🚀 go-pugleaf

In article <63058@mimsy.umd.edu>, stewart@cs.umd.edu (G. W. Stewart) writes:
> In article <1992Dec24.110843.29860@cv.ruu.nl> ger@cv.ruu.nl (Ger Timmens) writes:
> #I want the singular value decomposition of a 3x3 matrix.
> #I currently use the algorithm of numerical recipes.
> #However I think a much simpler algorithm should be out there.
> #
> #Any pointers ?
> 
> You've run into a situation that frustrates a lot of people.  In
> principle, it should be possible to solve eigenvalue (or singular
> value) problems of order 2, 3, and 4 directly using the formulas for
> solving quadratic, cubic, and quartic equations.  In practice, though,
> the complexity of the formulas makes the effort practical only for 2x2
> problems.  And even then the difficulties are great.  When Charlie Van
> Loan (of Golub and Van Loan fame) was a graduate student he produced a
> forty page manuscript entitled "An Algorithm for the Generalized
> Matrix Eigenvalue Problem {$Ax=\lambda Bx$} for the Important Case
> {$N=2$}", and it was none too short.  You will probably do well to
> stick with general code.
> 
> Not that I recommend the Numerical Recipes code.  I've been told that
> it is a modification of the LINPACK code, the modifications causing
> it to fail in some cases.  I would stick with the LINPACK or LAPACK
> code which is available on netlib.
> 
> Pete Stewart
> 
===========
I agree 100% with what Pete Stewart says in general.
The fact that "the important case n=2" is doable is largely? because
the roots of the characteristic polynomial are always simple,
simple in the sense that they are small and easily computed.
However, for the case in question n=3, you could try to factor the
characteristic polynomial symbolically.  If your 3 by 3 matrix
has a special form, you might get lucky.  The formulae for
the singular values will be relatively simple if it factors.
If the characteristic polynomial does not factor, as Pete Stewart
incidates, the formulae will too complicated.
One last possibility to try (I have never tried to do this
for computing a svd, I've only tried it for computing eigenvectors,
but the priciple should work) is to let a variable alpha denote
the root of the characteristic polynomial.  Compute the svd
symbolically in terms of this symbol alpha.  Later, it 
will take on the 3 numerical values -- roots of the characteristic polynomial.

Michael Monagan