Solving [K]{x}={b} efficiently, when [K] is symmetric!

Hi,

I have a fully populated symmetric matrix [K] (like those found in the finite element method).. but to save space for big [K], only the upper triangular is stored (packed) DIRECTLY either in a rectangular matrix OR in a long single column vector, (nearly a factor of 2.0 savings in space this way).

The question: Is there a matlab m file for the upper triangular back substitution matrix used in a Gauss elimination LDU solve for solving linear equations like [K]{x}={b}

Thank you,

Answer 1

[PA00]

In general FEM matrix’s are symmetric but not fully populated, also if you write your matrix with attention to the FEM mesh you can most of the times make the [K] matrix to be a banded matrix.

Since your matrix is fully populated it is not advantageous to use sparse matrix methods and matlab does (like Bruno said) not have symmetric matrix storage capabilities.

You can always write a function to solve your particular matrix, there are some efficient FORTRAN subroutines in manuals that do that for very particular types of matrices and you can rewrite them to matlab however I suggest you write your own. I have written my own to solve FEM symmetric and banded matrices where I store only the upper diagonals into a rectangular matrix and then solve it using Gaussian elimination code with a small twist to only reach that banded part. This was done to use less memory storing the matrix and use less processing time to solve the system.

Anyways, for your specific question you can use “linsolve(A,B,opts)” where in opts you state the type of A matrix you are inserting like a positive definite and upper triangular matrix (see the help file to see how it works).

This function works nice however has a bit of a downside, it does not accept matrix’s stored in a sparse system. It would be great if matlab made a specific matrix store system for symmetric matrix (and banded also if it was not much to ask) for memory savings and also specific solving code for faster solving.

Answer 2

[Bruno Luong]

Short answer no.

Long answer:

MATLAB does not have a mechanism of storing symmetric matrix (saving by a factor of 2 is probably not worth the effort).

Long answer: the CHOL command looks only at the upper half of your matrix, but as stated above you have to provide the full matrix, so I can't see how it helps you, without even look at the requirement of definite positiveness of the matrix.

BTW, FEM matrix is usually sparse. Now that is something worth the effort.

But you should be aware that coding a half of fully-populated matrix in sparse will take even more memory.

To summarize: just don't bother if you want to save half of fully populated matrix.

Bruno