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?



Decompositions of sparse symmetric matrices and methods for solving large linear equations
I agree that this is a better question for scicomp.stackexchange.com. 


1. Maybe. It depends on the sparsity structure of your particular matrix and the actual numerical values of the nonzero elements. You won't really know until you try.
2. Not in any way that I'm aware of.
3. Direct factorization (using a sparse LU factorization routine) is generally more accurate than iterative methods for problems like this, but you're getting to a size range where direct factorization may not be practical. The alternative is to switch to an iterative method, preferably with a good preconditioner (perhaps an incomplete LU factorization.)


Before you invest a lot of effort into installing a library for sparse LU, I'd suggest taking your system of equations (or a smaller version that may be of more manageable size) into MATLAB and using the sparse factorization tools available in MATLAB to see how amenable the problem is to this approach.


