home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / sci / math / numanal / 3692 < prev    next >
Encoding:
Text File  |  1992-12-28  |  2.9 KB  |  60 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!chx400!bernina!neptune!monagan
  3. From: monagan@inf.ethz.ch (Michael)
  4. Subject: Re: SVD implementation
  5. Message-ID: <1992Dec28.195602.17825@neptune.inf.ethz.ch>
  6. Summary: symbolic approach
  7. Sender: news@neptune.inf.ethz.ch (Mr News)
  8. Nntp-Posting-Host: rutishauser-gw.inf.ethz.ch
  9. Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
  10. References: <1992Dec24.110843.29860@cv.ruu.nl> <63058@mimsy.umd.edu>
  11. Date: Mon, 28 Dec 1992 19:56:02 GMT
  12. Lines: 46
  13.  
  14. In article <63058@mimsy.umd.edu>, stewart@cs.umd.edu (G. W. Stewart) writes:
  15. > In article <1992Dec24.110843.29860@cv.ruu.nl> ger@cv.ruu.nl (Ger Timmens) writes:
  16. > #I want the singular value decomposition of a 3x3 matrix.
  17. > #I currently use the algorithm of numerical recipes.
  18. > #However I think a much simpler algorithm should be out there.
  19. > #
  20. > #Any pointers ?
  21. > 
  22. > You've run into a situation that frustrates a lot of people.  In
  23. > principle, it should be possible to solve eigenvalue (or singular
  24. > value) problems of order 2, 3, and 4 directly using the formulas for
  25. > solving quadratic, cubic, and quartic equations.  In practice, though,
  26. > the complexity of the formulas makes the effort practical only for 2x2
  27. > problems.  And even then the difficulties are great.  When Charlie Van
  28. > Loan (of Golub and Van Loan fame) was a graduate student he produced a
  29. > forty page manuscript entitled "An Algorithm for the Generalized
  30. > Matrix Eigenvalue Problem {$Ax=\lambda Bx$} for the Important Case
  31. > {$N=2$}", and it was none too short.  You will probably do well to
  32. > stick with general code.
  33. > 
  34. > Not that I recommend the Numerical Recipes code.  I've been told that
  35. > it is a modification of the LINPACK code, the modifications causing
  36. > it to fail in some cases.  I would stick with the LINPACK or LAPACK
  37. > code which is available on netlib.
  38. > 
  39. > Pete Stewart
  40. > 
  41. ===========
  42. I agree 100% with what Pete Stewart says in general.
  43. The fact that "the important case n=2" is doable is largely? because
  44. the roots of the characteristic polynomial are always simple,
  45. simple in the sense that they are small and easily computed.
  46. However, for the case in question n=3, you could try to factor the
  47. characteristic polynomial symbolically.  If your 3 by 3 matrix
  48. has a special form, you might get lucky.  The formulae for
  49. the singular values will be relatively simple if it factors.
  50. If the characteristic polynomial does not factor, as Pete Stewart
  51. incidates, the formulae will too complicated.
  52. One last possibility to try (I have never tried to do this
  53. for computing a svd, I've only tried it for computing eigenvectors,
  54. but the priciple should work) is to let a variable alpha denote
  55. the root of the characteristic polynomial.  Compute the svd
  56. symbolically in terms of this symbol alpha.  Later, it 
  57. will take on the 3 numerical values -- roots of the characteristic polynomial.
  58.  
  59. Michael Monagan
  60.