Strassen algorithm [Edit]

Hello,

I am using the Strassen algorithm for matrix multiplication inside my multiple linear regression solver, so what about its numerical stability ?


Read this:

"We begin by discussing Strassen-like algorithms, based on recursive partitioning of matrices into the same number of blocks. We prove that all such algorithms are stable"


Read the following paper:

http://www.cs.cornell.edu/~rdk/papers/matmul.pdf


You can download my multiple linear regression solver from:

https://sites.google.com/site/aminer68/multiple-linear-regression


Thank you,
Amine Moulay Ramdane.

Edited by: Amine Moulay Ramdane on Oct 30, 2014 7:03 AM
0
Amine
10/30/2014 2:04:00 PM
embarcadero.algorithms 211 articles. 0 followers. Follow

4 Replies
1049 Views

Similar Articles

[PageSpeed] 3

Hello,


I am also using LU factorization to compute the inverse matrix inside my multiple linear regression solver, so what about its numerical stability ?


Read this:


"The LU factorization is numerically stable in practice, and produces a reasonable growth factor."


Read here on 3.1:

http://www.netlib.org/lapack/lawnspdf/lawn259.pdf



Amine Moulay Ramdane.




> {quote:title=Amine Moulay Ramdane wrote:}{quote}
> Hello,
> 
> I am using the Strassen algorithm for matrix multiplication inside my multiple linear regression solver, so what about its numerical stability ?
> 
> 
> Read this:
> 
> "We begin by discussing Strassen-like algorithms, based on recursive partitioning of matrices into the same number of blocks. We prove that all such algorithms are stable"
> 
> 
> Read the following paper:
> 
> http://www.cs.cornell.edu/~rdk/papers/matmul.pdf
> 
> 
> You can download my multiple linear regression solver from:
> 
> https://sites.google.com/site/aminer68/multiple-linear-regression
> 
> 
> Thank you,
> Amine Moulay Ramdane.
> 
> Edited by: Amine Moulay Ramdane on Oct 30, 2014 7:03 AM
0
Amine
10/30/2014 2:26:23 PM
> I am also using LU factorization to compute the inverse matrix inside my multiple linear regression solver, so what about its numerical stability ?

Generally speaking without geting into much detail:
Of course LU is numerically stable but that has nothing to do with the problem domain itself. SVD is the tool to go since it allows per definition to
do deep error analysis per se. E.g. If you want to invert a "bad" behaving matrix LU will simply tell you "can't do" wheras SVD will provide
you information within the singular values which can be exploited to still find a least squares answer. For example if a singular value is very
small it is set to zero instead of inverted and left as is for further processing and still you have your least squares solution at hand.
If you do it by LU or whatever solution you might get into troubles especially if you start forming some kind of covariance matrix A*A' - if there is a lot of linear
dependence you will badly fail to calculate the inversion properly without doing it by SVD
Check out http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse which shows a few algorithms to calculate the pseudoinverse.

ftp://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accuracy%20and%20Stability%20of%20Numerical%20Algorithms.pdf

In terms of speed SVD is of course the worst choice but again I favour stability over speed so if the data you are processing is behaving nicely and you
have enough memory by hand do the direct approach if not I would suggest to perform the operating using SVD.
Also in my projects I follow the simple rule to avoid any matrix inversion if possible. 

kind regards
  Mike
0
Michael
11/2/2014 2:08:43 PM
[mobile prepaid recharge|www.videocontelecom.com] 

Videocon Telecommunications Limited, a Videocon group company offers GSM mobile services GSM service under the brand name Videocon. The services are already up and running in Punjab*, Gujarat, Haryana, Madhya Pradesh and soon will be present across the country.

The Videocon Group is a $4 billion, global business conglomerate with a strong presence in Household Consumer Goods, Oil & Gas, Retail, Telecom, DTH and the Power sector.

The Videocon group has constantly leveraged a culture of innovation to develop a range of market re-defining products. The Group has several manufacturing facilities globally and R&D centers spread across Americas, Europe and Australasia that are constantly working towards creating global quality products deploying the most up-to-date technology.

Videocon has one of the largest distribution networks in India with a nation-wide presence.
0
umesh
12/24/2014 9:48:32 AM
Rudy,

Please delete this SPAM!  

-- 

   Q 

1.19.1.372  (Q's Broken Toolbar.)
0
Quentin
12/24/2014 7:21:10 PM
Reply:

Similar Artilces:

algorithm
hi every one, can anybody help me to validate this long number belong to this sequence . The sequence as below, if u could see the pattern, it add 1 to the 2nd last number and reset last digit to 0 when it hit 6. See the sequence, and i need to come out with the pattern formula, so that i could validate any sequence given whether it match the pattern or not... thanks all... Sequence :- 5277 2042 5277 2053 5277 2064 5277 2075 5277 2086 5277 2090 Hi, you may get some help from here http://regexlib.com/DisplayPatterns.aspx http://www.regular-expressions.info/Mehedi HasanMark as answer...

MOVED: Strassen algorithm
Moved to: embarcadero.public.algorithms or: https://forums.embarcadero.com/thread.jspa?threadID=109805 -- Rudy Velthuis http://www.rvelthuis.de "Gravity cannot be held responsible for people falling in love." -- Albert Einstein ...

My new concept and algorithms [Edit]
Hello, I want to talk to you about my new inventions that are my SemaMonitor and my SemaCondvar algorithms... I have invented those new concepts and algorithms and i want to explain to you what are they and what are there strength.. My SemaMonitor object combines all charateristics of a Semaphore and an eventcount, the EventCount look like the Windows Event Object, But you will notice that my new concept and algorithm called SemaMonitor is more powerful than a Windows Event Object alone and more powerful than the Semaphore alone, cause when you are sending the sig...

About my parallel sort algorithms [Edit]
Hello, As you have noticed i have implemented a parallel sort library and i have done some benchmark on it, and as you have noticed it can not scale much than 8X on multicore processors, the reason is simple, cause by nature the parallel sorts algorithms of my parallel sort library are limited by the serial part of the Amdahl's law that is the memory transfers from the memory to the L2 caches, so what is the solution then to make my parallel sort library to scale more on multicore CPUs ? you have to make it NUMA-aware and to make it scale on NUMA by parallelizing the memory transfer...

My Parallel Sort algorithm [Edit]
Hello... I have took a look at the following paper(it is a parallel sort algorithm): https://software.intel.com/en-us/articles/an-efficient-parallel-sort-algorithm I think my Parallel Sort library is also scalable and very efficient, cause my parallel sort algorithm uses two steps: the sorting step and the merging step, and you have to know that i have completly parallelized the sorting step and also i have completly parallelized the merging step, so it makes my parallel sort algorithm very efficient and scalable and very good, and it is better and more scalable than my ...

An HTML5 platform to animate algorithms [Edit]
I made a website (my master project at Technical University of Graz) where you can find animations of some algorithms. It is made with SVG/Javascript. You can run/pause/step/back an algorithm and see the pseudo code variables changing in real time. It should be very helpful for Bsc students and also teachers can use it during lectures. The site is called: alg0rithms.com (0 = zero) I'm waiting for your feedbacks... Edited by: Vorname Nachname on Nov 7, 2013 11:25 AM Edited by: Vorname Nachname on Nov 7, 2013 11:26 AM Vorname, | The site is called: alg0rithms.com (0 = ...

I need an Algorithm for my mapping application [Edit]
Hi All, I know the Lat and Lon for point X1Y1. I want to find the the Lat and Lon for a point that lies at a specified distance from and on a specified radial from X1Y1. Example: X2Y2 = 10 units form X1Y1 on the 270 degree radial relative to X 1Y1. Here is the equation I use to get distance between points: function TfrmMap.mDistanceBetween (X1: double; Y1: double; X2: double; Y2: double; pRadius: double): double; var R: double; begin R := 57.2958; // convert to radians Result := pRadius * ArcCos((Sin(X1/R) * Sin(X2/R)) + (Cos(X1/R) * Cos(X2/R) * Cos((Y2/R) - (...

Problem in Algorithm section (Wind Distance Interpolation) [Edit]
This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. --JivePart=_a0025.zeB8CwDOH5aMJzMl Content-Type: text/plain; charset="Utf-8" I've attached the spreadsheet to show an example of what I need. I hope this helps. Regards, Bryan Edited by: Bryan Ray on May 26, 2014 10:31 AM --JivePart=_a0025.zeB8CwDOH5aMJzMl-- This message is in MIME format. Since your mail reader does not understand this format, some or all of this message may not be legible. --JivePart=_a0095.zeB8CwDOH5aM...

Nanoprobe Algorithm
Hi, It would be very educative if someone could request Steve to discuss / show the nanoprobe algorithm ? In fact, wouldn't it be really kewl if a new group on algorithm was started ? I think it would be very constructive & educative ? It's okay to know that your box is in stealth mode, while you are online, but it is much better to know how this, supposed "stealth" is brought about. Just a thought. Enjoy! Debashish Mukherjee (HINT: If I want to contact you, I will do so) DebaM@yahoo.com wrote: > Hi, > It would be very educative if someone cou...

Recursive Algorithms
DEar All, I am developing a web crawler recursively. Meaning i have a method that goes through all the files and directories in my root directory reads their contents and displays them on the screen. I have a problem in it, such that, this script is using the cpu 100%, it is going recursively, then at each file, i am calling another method that uses "WebRequest and WebResponse" to read the contents of the files, since i have aspx files i need to read also. Is there any idea why i am having an error saying that Server Unavialable ? There is something wrong with this. do you...

RSA Algorithm
How to include RSA Algorithm in .net?   http://www.eggheadcafe.com/articles/20020630.asp http://www.example-code.com/vbdotnet/rsa.asp Dim str as String = "HelloThere" Dim RSA2 As RSACryptoServiceProvider = New RSACryptoServiceProvider() ' ---Load the private key--- RSA2.FromXmlString(privateKey) Dim EncryptedStrAsByt() As Byte =RSA2.Encrypt(System.Text.Encoding.Unicode.GetBytes(str),False) Dim EncryptedStrAsString = System.Text.Encoding.Unicode.GetString(EncryptedStrAsByt)  Best regards,Denis Chiochiu---------------------------------If you foun...

VIN algorithm
Does anyone know of a VIN algorithm? (To decode a given automobile VIN number using either the ISO or NA standard.) Thanks. Try here: http://www.autoinsurancetips.com/vin_number.htm Richard <planks> wrote in message news:44da372b.5307.1681692777@sybase.com... > Does anyone know of a VIN algorithm? (To decode a given > automobile VIN number using either the ISO or NA standard.) Google hits upon this page http://www.autoinsurancetips.com/vin.htm and wikipedia's page at http://en.wikipedia.org/wiki/Vehicle_identification_number [espe...

Convertion algorithme
I want to convert the PBUnits values to Pixels without using the UnitsToPixels function. Thanks Vincent Why? -- Simon Caldwell Get Real Systems Ltd Holtby Manor, Stamford Bridge Road, York, YO19 5LL Tel 01904 481999 Fax 01904 481666 Visit us at www.getrealsystems.com Specialists in e-Procurement and supply chain technology "Vincent Fabritius" <VFabritius@isagri.fr> wrote in message news:tObv4UnlAHA.258@forums.sybase.com... > I want to convert the PBUnits values to Pixels without using the UnitsToPixels > function. > > Thanks > Vince...

ZIP algorithm
Hi, Is there any (free?) DLL (or OCX) with collection of functions to operate ZIP (or RAR) archives? Regards, CB WinZip (not free, but dirt cheap) has a new command-line interface that allows to to zip/unzip files. WinZip also supports other compression formats like TAR, JAR, GZ, etc. The RAR format has many shareware utilities you can use -- CNet's download.com has a few. -- <hopethishelps /> Roy Kiesler [TeamSybase] mySybase -- http://my.sybase.com http://cgi.exp.com/noauth/advisor_profile.cgi?adv_id=512231 "cbnet" <cbnet@wp.pl> wrote in mes...

Web resources about - Strassen algorithm [Edit] - embarcadero.algorithms

Algorithm - Wikipedia
Flow chart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named ...

Netflix Dropping Its “One-Size-Fits-All” Streaming Algorithm
... might have found a better way to make sure that still happens, while using less data. Variety reports that after four years of tests and algorithm ...

An algorithm can tell if your face is forgettable
Some faces are more memorable than others. The brain processes visual cues to decide if a face or an image will stay lodged in the memory bank. ...

Netflix Updates Algorithm Policy, May Solve Streaming Issues
Instead of its old blanket policies, Netflix now is looking at all its video presentations and assigning appropriate encoding algorithms to each ...

Carly Fiorina Says We're Not Using the Right Algorithms to Catch Terrorists
... to work with the government on security issues because she “knows them.” And then she insisted that the government is using the wrong algorithms ...

'Ex Machina,' here we come: A new algorithm helps computers learn the way we do
Machine learning is all about getting computers to "understand" new concepts, but it's still a pretty inefficient process, often requiring hundreds ...

See How Memorable Your Profile Pictures Are With MIT's MemNet Algorithm
... on social networks and dating sites , a memorable picture is essential. The Massachusetts Institute of Technology claims their new MemNet algorithm ...

MarTech Today: True Influence Opens Up, Curiosity Algorithms & Topsy Shuts Down
Here’s our daily recap of what happened in marketing technology, as reported on Marketing Land and other places across the web. From Marketing ...

An Algorithm Can Tell How Forgettable Your Selfies Are
MemNet uses artificial intelligence to find patterns in what humans remember the most.

10 amazing algorithms
Figuring out mysteries Image by Flickr Cyber technology couldn’t get by without algorithms to encrypt, analyze metadata and find traffic anomalies, ...

Resources last updated: 12/24/2015 12:30:18 AM