Watch, Follow, &
Connect with Us

For forums, blogs and more please visit our
Developer Tools Community.


Welcome, Guest
Guest Settings
Help

Thread: Strassen algorithm



Permlink Replies: 4 - Last Post: Jun 7, 2016 2:31 AM Last Post By: acemary mary Threads: [ Previous | Next ]
Amine Moulay Ra...

Posts: 599
Registered: 2/12/10
Strassen algorithm
Click to report abuse...   Click to reply to this thread Reply
  Posted: Oct 30, 2014 6:38 AM
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

Amine Moulay Ra...

Posts: 599
Registered: 2/12/10
Re: Strassen algorithm
Click to report abuse...   Click to reply to this thread Reply
  Posted: Oct 30, 2014 7:26 AM   in response to: Amine Moulay Ra... in response to: Amine Moulay Ra...
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.

Amine Moulay Ramdane wrote:
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

Michael Rabatsc...

Posts: 125
Registered: 1/22/07
Re: Strassen algorithm
Click to report abuse...   Click to reply to this thread Reply
  Posted: Nov 2, 2014 6:08 AM   in response to: Amine Moulay Ra... in response to: Amine Moulay Ra...
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
shiny victor

Posts: 2
Registered: 5/4/16
Re: Strassen algorithm
Click to report abuse...   Click to reply to this thread Reply
  Posted: May 19, 2016 3:34 AM   in response to: Michael Rabatsc... in response to: Michael Rabatsc...
binary search is a searching algorithm.in each step.the agorithm compares the input element x with the value of the middle element in array.if the value match,return the index of middle.otherwise.if x is less than the middle element.then the algorithm recurs for left side middle element.else recurs for right side middle element.

Dot net Training in Chennai | Cloud Computing Training in Chennai | Linux Training in Chennai | Salesforce Training in Chennai

Edited by: shiny victor on May 19, 2016 3:44 AM
acemary mary

Posts: 12
Registered: 2/23/16
Re: Strassen algorithm
Click to report abuse...   Click to reply to this thread Reply
  Posted: Jun 7, 2016 2:30 AM   in response to: Amine Moulay Ra... in response to: Amine Moulay Ra...
it is very easy to do 2x2 and 3x3 matrix multiplications. but how to do mxm or pxq matrix multiplications using Strassen algorithm....

tried some thing... but stuck middle.. not working http://www.traininginsholinganallur.in/php-training-in-chennai.html

still trying.. posted this because thought someone will help for me... http://www.traininginsholinganallur.in/web-designing-training-in-chennai.html

expected output
Code:

Enter the number of rows and columns of first matrix: 3 3
Enter the number of rows and columns of second matrix: 3 3 http://www.besanttechnologies.com/training-courses/web-designing-training

Enter the elements of first matrix: 1 2 3 4 5 6 7 8 9
Enter the elements of second matrix: 1 2 3 4 5 6 7 8 9

Matrix Multiplication:
30 36 42
66 81 96
102 126 150

Edited by: acemary mary on Jun 7, 2016 2:30 AM

Legend
Helpful Answer (5 pts)
Correct Answer (10 pts)

Server Response from: ETNAJIVE02