Thread Subject: cholesky decomposition on sparse matrix

I have two sparse matrix.
Their sizes are the same:11027*11027.
I used spy to observe them and found the structures of them
are similar and the nz are almost same.
I use cholesky to factor them by linfactor function wirtten
by Timothy A. Davis which runs very well in my linear equation.
I found the L of them are totally different:
nz of one L is only 77229 but another L is 163078.
I don't know how to analyze them.
 

"yunzhi cheng" <sjtu_yh@yahoo.com> wrote in message
<fn8krc$q4s$1@fred.mathworks.com>...
> I have two sparse matrix.
> Their sizes are the same:11027*11027.
> I used spy to observe them and found the structures of them
> are similar and the nz are almost same.
> I use cholesky to factor them by linfactor function wirtten
> by Timothy A. Davis which runs very well in my linear
equation.
> I found the L of them are totally different:
> nz of one L is only 77229 but another L is 163078.
> I don't know how to analyze them.
>
>

spy tells you almost nothing about a sparse matrix and how
it might be ordered. You don't have a 11000 by 11000 pixel
display, and even if you did you wouldn't be able to
interpret by looking at it.

Ordering a sparse matrix is an NP-hard problem; there are no
guarantees.

Thanks, Tim.
Your method of linfactor is really good.

So there are two methods for my problem.
One can form the matrix whose L in cholesky factorization is
much sparser than another one.
But it is just from the practical matrix.
It is harder to prove it.

I wonder how to prove that that method generate the matrix
which can lead sparser L.

"yunzhi cheng" <sjtu_yh@yahoo.com> wrote in message
> I wonder how to prove that that method generate the matrix
> which can lead sparser L.
>

Except for very limited cases (2D,3D meshes with nested
dissection, for example), what your are asking for is
essentially impossible.

Ordering a matrix is an NP-hard problem; solving the problem
exactly would time greater than the lifetime of the
universe. Heuristics are thus used instead, and these
heuristics have absolutely no provable guarantee as to their
ordering quality (number of nonzeros in L).