4

I have a system Ax = b, where B is a constant, but A keeps changing by small amounts in each iteration. I am using UMFPACK 5 to solve this linear system again as again as A changes. I can do the above in two ways:

  1. Compute the symbolic and numeric factorization of matrix A ONLY in the beginning, and use this numeric object for solving Ax = b in each iteration (of course in sparse matrix representation, Ax changes as A changes. Ap and Ai remain same).
  2. Compute the symbolic and numeric factorization of matrix A IN EACH iteration (i.e. a new numeric object as A changes) and use this new numeric object to solve Ax = b.

Which of the above ways is correct? I am getting completely different answers (as expected) for the above two procedures. Any help or comment is appreciated. Thanks.

Chatter
  • 193
  • 8

2 Answers2

2

The symbolic factorization depends only on the sparsity pattern (Ap and Ai in the notation of UMFPACK). The numeric factorization depends on the actual values (Ax). So you need to compute the symbolic factorization only once, but you need to re-compute the numeric factorization in each factorization.

The documentation of UMFPACK shows that this is a slight simplification of reality. In fact, UMFPACK does use the actual values to do the symbolic factorization, but it only distinguishes between 'small' and 'large' values. So if the matrix A changes only a little, that does not matter. If the values (Ax) change by so much that a previously 'small' value becomes large, or the other way around, then the symbolic factorization may change. However, if you use the old symbolic factorization with the new Ax, you will still get the correct numeric factorization and the correct solution, though UMFPACK is (presumably) more efficient if you use the new symbolic factorization.

So, whether you want to recompute the symbolic factorization depends on how long it takes to compute the symbolic factorization, and how much quicker the numeric factorization is if you use the symbolic factorization with the correct Ax. My guess would be that you do not want to recompute the symbolic factorization if you change only a couple of values, but you need to benchmark.

Jitse Niesen
  • 4,492
  • 26
  • 23
  • Hey, thanks for the detailed overview. :) My A matrix is changing such that less than 4 entries are subtracted/added each time out of a 10kX10k matrix, but this change may make some (upto 2) entries of A 'small' i.e close to zero. In that case maybe I should recompute the symbolic and numeric factorization again. Also, if possible, can you please elaborate what do u mean when u say : "if the values are wrong you still get a correct result". Thanks again for your help. – Chatter Mar 02 '12 at 22:59
0

The second way is correct, as if you computing numeric factorization you should repeat it in each iteration.

Seagull
  • 3,319
  • 2
  • 31
  • 37