seshacha@uokvax.UUCP (12/24/84)
A few days back I was searching for a paper
on the following subject:
"Gaussian elimination not optimal"
As I could not find the journal "Numerical Math"
(English version),I was left at bay.
Could anyone throw some light on this subject?
P.S.
Please don't fill my mail
with heavy stuff..ags@pucc-i (Dave Seaman) (12/26/84)
> A few days back I was searching for a paper > on the following subject: > > "Gaussian elimination not optimal" > > As I could not find the journal "Numerical Math" > (English version),I was left at bay. > > Could anyone throw some light on this subject? The immediate problem that is addressed by the paper is matrix multiplication. A faster algorithm for multiplying matrices also leads to faster algorithms for solving linear systems. The method has some theoretical interest, but is not the basis of any practical application at the present time. The key is that a pair of 2-by-2 matrices can be multiplied with only seven multiplications instead of the usual 8 (method given at end of article). The formula makes no use of commutativity and can therefore be applied recursively to block matrices. For large matrices, the number of multiplications can be reduced from the usual N**3 (where N is the order of the matrix) to N**p, where p is the log (base 2) of 7, or approximately 2.81. The price for the slight reduction in the number of multiplications is a substantial increase in additions and subtractions, plus the recursion overhead. The algorithm is somewhat wasteful when N is not a power of 2, since you must pad with zeros to make the method work. The assumption is that adds and subtracts on block matrices are relatively inexpensive compared to multiplies, and that the method will be practical for sufficiently large matrices. ----------------------------------------------------------------------- The Strassen Algorithm ( a11 a12 ) ( x11 x12 ) Let A = ( ) and X = ( ) be block matrices. ( a21 a22 ) ( x21 x22 ) First compute: I = (a11 + a22) * (x11 + x22) II = (a21 + a22) * x11 III = a11 * (x12 - x22) IV = a22 * (-x11 + x21) V = (a11 + a12) * x22 VI = (-a11 + a21) * (x11 + x12) VII = (a12 - a22) * (x21 + x22). ( y11 y12 ) Then the product Y = A*X = ( ) is given by: ( y21 y22 ) y11 = I + IV - V + VII y21 = II + IV y12 = III + V y22 = I + III - II + VI. Reference: Volker Strassen, "Gaussian Elimination Is Not Optimal", Numer. Math., 13(1969), pp. 354-356. -- [This is my bugkiller line. It may appear to be misplaced, but it works.] Dave Seaman My hovercraft is no longer full of ..!pur-ee!pucc-i:ags eels (thanks to my confused cat).