🚀 go-pugleaf

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.

There's a method using orthogonalization by plane rotations from
the book by J. C. Nash, "Compact Numerical Methods for Computers:
Linear Algebra and Function Minimisation," Wiley 1979.  If you use
it to orthogonalize the columns, you only get a basis for the
column space, not its orthogonal complement, though you get the
complete row-space and null-space.  I am pretty sure it
is not as efficient as the standard SVD algorithm in Linpack,
but it is very simple to program.

I used Nash's technique in an application involving an N-by-3 coefficient
matrix for linear predictive coding.  By some simple preprocessing
to remove the constant LPC coefficient, the matrix was transformed to
N-by-2.  With just two columns, only one plane rotation is needed to
get the SVD, and you can even explicitly compute the singular values
without performing the whole SVD.  But I think that in general,
an N-by-3 matrix has no such simple solution.

I've implemented Nash's algorithm in Fortran, Pascal, and C, and
can mail you code if you want it.

...Rick			perry@vu-vlsi.ee.vill.edu

Dr. Rick Perry, Department of Electrical and Computer Engineering
Villanova University, Villanova, PA 19085, 215-645-4969, hm: 215-259-8734

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

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