Watch, Follow, &
Connect with Us

Developer Tools Community.

Welcome, Guest
Guest Settings

Replies: 4 - Last Post: Jun 7, 2016 2:31 AM Last Post By: acemary mary
 Posts: 599 Registered: 2/12/10
 Strassen algorithm 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
 Posts: 599 Registered: 2/12/10
 Re: Strassen algorithm Posted: Oct 30, 2014 7:26 AM   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
 Posts: 125 Registered: 1/22/07
 Re: Strassen algorithm Posted: Nov 2, 2014 6:08 AM   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
 Posts: 2 Registered: 5/4/16
 Re: Strassen algorithm Posted: May 19, 2016 3:34 AM   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
 Posts: 12 Registered: 2/23/16
 Re: Strassen algorithm Posted: Jun 7, 2016 2:30 AM   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