From: hrubin@odds.stat.purdue.edu (Herman Rubin) Subject: Re: Diagonalization and SVD newbie question Date: 5 Oct 1999 12:40:31 -0500 Newsgroups: sci.math,sci.math.num-analysis Keywords: computing some matrix factorizations In article <37F96A41.2B02DEAD@polyu.edu.hk>, Hankel O'Fung wrote: >Hi, >(1) If A is a nxn real positive definite matrix, what are the best known >algorithms for do decomposing A into QDQ^t, where D is diagonal and Q is >orthogonal (yes, I need not only the eigenvalues but also Q)? Are these >algorithms stable? Any references? Positive semidefinite does not make that much difference, as one can add a multiple of the identity to make it so without changing the solution except in the same manner. The one most used at present is the use of Householder transformations to reduce A to tridiagonal form and then the QR method to finish the job. >(2) For a general real mxn matrix B without any special structure, what >are the best known algorithms for finding the singular value >decomposition of B? Again, are these algorithms stable? Any reference? These are similar. >From some textbooks, I learn that the factorization in (1) can be made >O(n^2) and SVD O(mn^2). However, I don't know if any significant >improvements were made recently. The work to do the Householder reduction os O(n^3), and for each step in the QR method, O(n^2). the number of steps needed for the QR method is usually considerably larger than n. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558