Wednesday, May 21, 2008

Timings on Cholesky

It is quite amazing how fast these three alternatives for Cholesky are. Here is a model to time the performance and accuracy. Some results are listed below.
MethodTimeAccuracyTimeAccuracyTimeAccuracy

n=50n=100n=200
Nonlinear Equations0.1489.6e-80.9171.2e-48.9910.621
External Solver0.0241.6e-130.0251.9e-100.0561.4e-5
GAMS Algorithm0.0341.9e-130.4826.3e-117.5717.7e-6

I am surprised that the GAMS algorithm is competitive. Notice the accuracy issues when using nonlinear equations due to ill-conditioning of the system of non-linear equations (small changes in a(i,j) lead to large changes in L(i,j)).


Here is some info about the external solver:


c:\>cholesky
CHOLESKY: matrix decomposition A=LL^T
Usage
> cholesky gdxin i a gdxout L
where
gdxin : name of gdxfile with matrix
i : name of set used in matrix
a : name of 2 dimensional parameter inside gdxin
gdxout : name of gdxfile for results (factor L)
L : name of 2 dimensional parameter inside gdxout

Calculates the Cholesky decomposition A=LL^T of a symmetric
positive definite matrix A=a(i,j) where i and j are aliased sets.
L will contain the Cholesky factor L(i,j)


C:\>