# Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form

$$A_{n\times n}\cdot x=1_n$$

where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each row. This makes its size barely manageable, but inverting it is infeasible, and I'm not sure which decomposition suitable for solving linear equations would lead to sparse matrices.

Thus the questions:

1) Any hope that $LU$ decomposition of a symmetric sparse matrix would be sparse?

2) Is it possible to take advantage that r.h.s. is a scalar to simplify solution of the above equation?

3) What would be the best numerically stable algorithm to handle linear equations of that size?

• this question is more suitable for scicomp.stackexchange.com May 9, 2014 at 18:45
• I think the question is perfectly well suited to MO. I also think OP might want to consider "black box linear algebra": see, e.g. persweb.wabash.edu/facstaff/turnerw/Presentations/rhit-2003.pdf May 9, 2014 at 20:10
• You will almost certainly want to use an iterative method. There are good libraries for this. For instance, if you set your problem up in PETsc, you can try dozens of methods at the flip of a switch, and you can run them in parallel on whatever large machine you may have. The PETSc devs are very willing to help select a method if you ask. Sep 20, 2014 at 12:35