5
$\begingroup$

For instance, in MUMPS there is option to scale matrix s.t. all rows/columns have the same norm. This claims to decrease condition number and improve numerical properties of the matrix: ftp://cuter.rl.ac.uk/pub/reports/adruRAL2008013.pdf

Can anybody explain whether it can be used as a preconditioner and how efficient would it be?

Improve this question
$\endgroup$
  • $\begingroup$ Isn't this simply the Jacobi preconditioner? $\endgroup$ – shuhalo Mar 18 '12 at 16:24
4
$\begingroup$

Most preconditioners effectively do this scaling internally. Jacobi scales to put 1 on the diagonal (or for absolute row sums of 1). Scaling is more important when using more sophisticated preconditioners such as geometric multigrid or those based on approximate Schur complements (where matrix entries are not available for algebraic scaling). Additionally, even if the preconditioner corrects the scaling, the unpreconditioned norm (and nonlinear residuals) will still be misleading.

For factorization, it can be helpful for numerical stability to apply a pre- and post-scaling before starting the factorization. You can do the same with an iterative solve, but it is relatively more expensive (because scaling--and later unscaling if you want to check a final residual--is similar to the cost of an iteration) compared to direct solvers which do much more work. This scaling also makes it difficult to use "physics-based" preconditioners.

Whenever possible, I recommend formulating your initial problem to be well-scaled. If that is not possible, or you want to experiment with linear algebra applied to a legacy application in which it would take significant effort to scale properly, scaling is a useful tool.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you. "Most preconditioners effectively do this scaling internally", - is this true for the case with big material property contrasts and large ratios between grid cells/elements (grid stretching)? I imagine that in this case scaling can be especially effective. $\endgroup$ – Alexander Mar 18 '12 at 14:52
  • $\begingroup$ Jacobi is the simplest preconditioner and it either puts $1$ on the diagonal or makes the absolute value row sums equal to $1$. It's not a matter of how big the jumps are, it's a matter of whether the preconditioner can be constructed stably without pre-scaling first. If the preconditioner can be constructed stably, it will generally correct the bad scaling, except in cases that use auxiliary information like geometric multigrid with rediscretized coarse operators or Schur complement methods. $\endgroup$ – Jed Brown Mar 18 '12 at 15:36
2
$\begingroup$

The main reason that sparse direct LU factorisation packages (like MUMPS etc) involve a pre-processing step that scales and permutes large entries onto the diagonal is that it often reduces the number of dynamic pivoting operations required within the factorisation.

When the pivoting is restricted to the diagonal (or the diagonal blocks in a supernodal sense) it's possible to perform a static symbolic analysis for the factorisation as an initialisation step. This is often faster in general, but especially important for parallel implementations - check out this SuperLU paper that discusses the parallel implications.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.