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:
LU factorization of sparse matrices

Subject: LU factorization of sparse matrices

From: John Montgomery

Date: 14 Jan, 2009 20:30:39

Message: 1 of 5

I'm not sure if this is some kind of error that I haven't been able to undo yet, but following the syntax from Matlab's user guide, I have a sparse, symetric matrix A, and I want to do the LU factorization of it. I enter:

[L,U,P] = lu(A);

And then the program seems to just hang forever. Ctrl+C didn't even stop it, I had to use Ctrl+Z to suspend it. Is there something that I'm doing wrong? I tried to let Matlab take as long as it needed, and I let it run last night after I fell asleep until whenever my connection with the server was timed out (I'm using Matlab remotely), but it still hadn't given me an answer. Any help here? Is it normal for this to take so long?

~John

Subject: LU factorization of sparse matrices

From: John D'Errico

Date: 14 Jan, 2009 21:25:03

Message: 2 of 5

John Montgomery <experimentmonty@gmail.com> wrote in message <15336137.1231965070192.JavaMail.jakarta@nitrogen.mathforum.org>...
> I'm not sure if this is some kind of error that I haven't been able to undo yet, but following the syntax from Matlab's user guide, I have a sparse, symetric matrix A, and I want to do the LU factorization of it. I enter:
>
> [L,U,P] = lu(A);
>
> And then the program seems to just hang forever. Ctrl+C didn't even stop it, I had to use Ctrl+Z to suspend it. Is there something that I'm doing wrong? I tried to let Matlab take as long as it needed, and I let it run last night after I fell asleep until whenever my connection with the server was timed out (I'm using Matlab remotely), but it still hadn't given me an answer. Any help here? Is it normal for this to take so long?
>
> ~John

What you have not said is how large is the matrix?
How sparse is it?

John

Subject: LU factorization of sparse matrices

From: Tim Davis

Date: 15 Jan, 2009 01:03:02

Message: 3 of 5

John Montgomery <experimentmonty@gmail.com> wrote in message <15336137.1231965070192.JavaMail.jakarta@nitrogen.mathforum.org>...
> I'm not sure if this is some kind of error that I haven't been able to undo yet, but following the syntax from Matlab's user guide, I have a sparse, symetric matrix A, and I want to do the LU factorization of it. I enter:
>
> [L,U,P] = lu(A);
>
> And then the program seems to just hang forever. Ctrl+C didn't even stop it, I had to use Ctrl+Z to suspend it. Is there something that I'm doing wrong? I tried to let Matlab take as long as it needed, and I let it run last night after I fell asleep until whenever my connection with the server was timed out (I'm using Matlab remotely), but it still hadn't given me an answer. Any help here? Is it normal for this to take so long?
>
> ~John

You are not allowing LU to permute the colums of A to improve the sparsity of L and U, and can suffer high fill-in as a result. Use this instead:

[L,U,P,Q]=lu(A)

insteadl. Also ... if it's symmetric you should use

Subject: LU factorization of sparse matrices

From: John Montgomery

Date: 15 Jan, 2009 02:40:05

Message: 4 of 5

The matrix that I'm using right now is 23,052 by 23,052, it has 1,143,140 nonzero entries, and you can see the rest of the details of it here:

http://www.cise.ufl.edu/research/sparse/matrices/Boeing/bcsstk36.html

As for letting LU permute the columns of A, I've already permuted the columns and rows of A to one of several pre-determined orderings, so I specifically don't want to let it re-permute A. After the LU factorization, what I plan to do is determine how much fill-in was produced and whether one ordering works better than another for reducing the amount of fill-in with LU factorization.

Subject: LU factorization of sparse matrices

From: Tim Davis

Date: 16 Jan, 2009 13:07:02

Message: 5 of 5

John Montgomery <experimentmonty@gmail.com> wrote in message <7195800.1231987238224.JavaMail.jakarta@nitrogen.mathforum.org>...
> The matrix that I'm using right now is 23,052 by 23,052, it has 1,143,140 nonzero entries, and you can see the rest of the details of it here:
>
> http://www.cise.ufl.edu/research/sparse/matrices/Boeing/bcsstk36.html
>
> As for letting LU permute the columns of A, I've already permuted the columns and rows of A to one of several pre-determined orderings, so I specifically don't want to let it re-permute A. After the LU factorization, what I plan to do is determine how much fill-in was produced and whether one ordering works better than another for reducing the amount of fill-in with LU factorization.

The probem is that LU will then permute the rows, for partial pivoting, which destroys the fill-reducing ordering. Since the matrix is symmetric positive definite, you should use chol, not lu.

Tags for this Thread

No tags are associated with 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