Cholesky decomposition

July 11th, 2006 ~ Posted in: Mathematics

I just learned about the Cholesky algorithm for testing whether a matrix A \in M_n is positive/ factoring a positive matrix in terms of a lower triangular matrix L \in M_n as A = LL^\star . This is something we should have learned in numerical methods for engineers– it seems extremely useful from what I’ve seen from just browsing the internet, and listening to the lecturer. In particular, the matrix that I was trying to show is positive definite in an earlier post:

\displaystyle A = \begin{pmatrix} t_1 & t_1 & \ldots & t_1 \\ t_1 & t_2 & \ldots & t_2 \\ & & \vdots & \\ t_1 & t_2 & \ldots & t_n \end{pmatrix},

in the special but representative case where t_i = i, has a very simple Cholesky decomposition: L is the lower triangular matrix of ones (with ones on the diagonal also).

Mathematics ~

One Response to “Cholesky decomposition”

  • 1. Peter Steeves
    December 8th, 2006 at 7:03 pm

    Hi, I am a geomatics Engineer. I began programming Cholesky’s algorithms in 1975. In 1977, I was able to solve 250,000 non-linear equations on a B2700 computer that had 128 Kilo Bytes of RAM. I authored “The Block Cholesky.” I am able to compute any block of the Inverse Matrix without computing all of the matrix. A Mathematics & Computer Science Professor told me it was impossible to solve the inverse by blocks; therefore, I did it. First man on Earth to do so. Actually, my algorithm is really simple. It solves the matrix by blocking it in 10×10, 20×20, or even 100×100 blocks. Only 3 blocks are required in RAM at any one time. This means my solution is only limited by the size of the hard drive and time. It’s quite fast even though it’s blocked. I adjusted 400 Kms of leveling data from Northern Nigeria in 0.75 seconds.

    See if you can find my papers at http://www.gssGeomatics.com. I’ll be adding more real soon. Right now I am developing a Least Squares solutions for leveling, horizontal control, and GPS.

    Peter Steeves, BSc, MSc, PhD
    Geomatics Engineer
    Mississauga, Ontario
    Canada

This entry was posted on Tuesday, July 11th, 2006 at 2:17 pm and is filed under Mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply