From: mittelmann@asu.edu (Hans Mittelmann) Subject: Re: QR and LU algorithms for eigenvalues Date: 9 Oct 2001 13:57:33 -0700 Newsgroups: sci.math.num-analysis Summary: Comparison of matrix factorizations for computing eigenvalues Hi, the LR (for left/right - in German, actually, not lower/upper) was invented before the QR algorithm by the Swiss Rutishauser. Good numerical linear algebra books such as Golub&VanLoan mention it. It is not as popular as QR due to the overall greater stability of orthogonal decompositions, but, in certain cases, for example, for symmetric matrices with Cholesky decompositions and special shifts it is extremely efficient. Hans Mittelmann ------------------------------------------------------------------------------- Denis Sevee wrote in message news:... > Hello, > The QR algorithm for computing eigenvalues involves (in part) the > iteration A1=Q1*R1 > A2=R1*Q1 > A2=Q2*R2 > A3=R2*Q2 > etc. > > I recently noticed that if you replace the QR decomposition by the LU > decomposition that this algorithm still works (given certain restrictions > on A). I couldn't find any discussion of using the LU algorithm for this > purpose. Can anyone give me a reference for this. > > Thanks > Denis Sevee ============================================================================== From: "William R. Frensley" Subject: Re: QR and LU algorithms for eigenvalues Date: Wed, 10 Oct 2001 13:59:16 -0500 Newsgroups: sci.math.num-analysis Let me point out that LR is described by Golub & van Loan, and originally by Wilkinson, but that these references very thoroughly deprecate the method. On the other hand, we have found it to be extremely effective for a rather particular class of problems. This happens to be tridiagonal matrices which are purely real and symmetric, except for nonzero imaginary parts in the corner diagonal elements. Such problems arise from discretizing a Helmholz equation with "transparent" boundary conditions. Now, the standard eigensystem toolkits have no way to deal with this system while preserving the tridiagonal structure. Since the problem is non-Hermitian, the standard packages produce a Hessenburg matrix. LR, on the other hand, preserves the tridiagonal sparsity structure, and with implicit shifts it converges as quickly on these complex eigenvalues as the implicit QR method does on the eigenvalues of a real symmetric tridiagonal. The lesson is that there are more effective algorithms available than the textbooks would lead you to believe. - Bill Frensley Hans Mittelmann wrote: [quote of previous message deleted --djr] ============================================================================== From: mittelmann@asu.edu (Hans Mittelmann) Subject: Re: QR and LU algorithms for eigenvalues Date: 11 Oct 2001 18:26:47 -0700 Newsgroups: sci.math.num-analysis You write Wilkinson wrote "originally" about it. Let me repeat again that the original description is by noone else than by the "inventor" H. Rutishauser. He wrote a number of papers about it, an example of one in English is H. Rutishauser, Solution of Eigenvalue Problems with the LR Transformation, Nat. Bur. Stand. Appl. Math. Ser. 49, 47-81 (1958) Hans Mittelmann ------------------------------------------------------------------------------- "William R. Frensley" wrote in message news:<3BC49A84.4E338F22@utdallas.edu>... [quote of previous message deleted --djr]