Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
cholesky decomposition on sparse matrix

Subject: cholesky decomposition on sparse matrix

From: yunzhi cheng

Date: 24 Jan, 2008 00:07:08

Message: 1 of 4

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.
 

Subject: cholesky decomposition on sparse matrix

From: Tim Davis

Date: 24 Jan, 2008 14:48:02

Message: 2 of 4

"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.

Subject: cholesky decomposition on sparse matrix

From: yunzhi cheng

Date: 26 Jan, 2008 22:35:03

Message: 3 of 4

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.

Subject: cholesky decomposition on sparse matrix

From: Tim Davis

Date: 28 Jan, 2008 12:50:17

Message: 4 of 4

"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).

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us