1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ this question is more suitable for scicomp.stackexchange.com $\endgroup$
    – guest
    Commented May 9, 2014 at 18:45
  • 1
    $\begingroup$ 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 $\endgroup$
    – Steve Huntsman
    Commented May 9, 2014 at 20:10
  • $\begingroup$ 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. $\endgroup$
    – David Ketcheson
    Commented Sep 20, 2014 at 12:35

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm curious- what approach did you decide on in the end? $\endgroup$
    – Brian Borchers
    Commented Sep 20, 2014 at 20:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .