19 votes
Accepted

Why does this preconditioner effectively reduce the condition number of a random SPD matrix?

If the eigenvalues of $A$ are $\lambda_1, \lambda_2, \dots,\lambda_n$, the eigenvalues of $A + \mu I$ are $\lambda_1 + \mu, \lambda_2 + \mu, \dots, \lambda_n + \mu$. It is an easy computation to ...
Federico Poloni's user avatar
15 votes

"Cookbook" about iterative linear solvers and preconditioners

Have a look at Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (Barrett et al.). You can find it here. Here's why I'm recommending this over other references: the ...
GoHokies's user avatar
  • 2,206
13 votes
Accepted

How to directly compute the inverse of an ill-conditioned dense matrix

Though it is a relatively rare situation when you actually have to calculate an inverse of the matrix, not all techniques were created equally. I would use the term badly-conditioned instead of ill-...
Anton Menshov's user avatar
  • 8,672
13 votes
Accepted

When do not use preconditioners for sparse linear system of equations?

In my experience, you always need (or better use) some form of preconditioning. The type and complexity of the precondition would vary depending on the task though. From Y. Saad, Iterative Methods for ...
Anton Menshov's user avatar
  • 8,672
12 votes
Accepted

role of initial guess for iterative linear solver

Practical experience shows that trying to get good initial iterates has little value. For example, in the context of solving partial differential equations, if you take the solution from one mesh, ...
Wolfgang Bangerth's user avatar
12 votes

Why does this preconditioner effectively reduce the condition number of a random SPD matrix?

The accepted answer is right: you are not making a preconditioner. To elaborate. For a matrix $A$, a preconditioner is a matrix $B$ such that $B^{-1}A$ has a smaller condition number than $A$. The ...
Victor Eijkhout's user avatar
8 votes
Accepted

Efficient implementation of preconditioners for iterative solvers

I don't particularly care for the notation $M^{-1}$ precisely because of the confusion you find yourself in. I (and others) simply call the preconditioner $P$. The point, however, is that for ...
Wolfgang Bangerth's user avatar
8 votes
Accepted

Why do many people use FDM method to solve Stokes equations, i.e., saddle point matrix?

The preconditioner for the FDM method that corresponds to the one you outline for the FEM (i.e., the Sylvester-Wathen approach) will still contain the Schur complement of the FDM matrix. The Schur ...
Wolfgang Bangerth's user avatar
6 votes
Accepted

Correct use of scipy's sparse.linalg.spilu

If $\mathbf L$ and $\mathbf U$ give an approximate factorization of $\mathbf A$, you wouldn't want to use $\mathbf P = \mathbf L\cdot \mathbf U$ as a preconditioner (that's approximately $\mathbf A$), ...
rchilton1980's user avatar
  • 4,862
6 votes
Accepted

Optimality of block-Jacobi preconditioner

Consider matrix a $2\times 2$ matrix $A$: $$ A=\left(\begin{array}{cc} 1 & 0\\ 2 & 1 \end{array}\right) $$ Singular values of $A$ are: $$ \sigma_1 = \sqrt{2}+1,\quad \sigma_2=\sqrt{2}-1 $$ ...
Anton Menshov's user avatar
  • 8,672
6 votes
Accepted

Iterative linear solver for "ugly" saddle point system

You should stick with GMRES, it is the only method that is essentially guaranteed to get a solution here. The real problem appears to be you need a better preconditioner. You could try sticking with ...
EMP's user avatar
  • 2,089
5 votes
Accepted

How to verify solution to pre-conditioned linear systems solver?

You've started with a singular linear system of equations $Ax=b$. As a practical matter, it's unlikely that $b$ lies exactly in the range of $A$, so at best you can find a least squares solution that ...
Brian Borchers's user avatar
5 votes

Correct use of scipy's sparse.linalg.spilu

This question has an example of how to create the preconditioner M with a scipy sparse matrix A of shape ...
Jeff's user avatar
  • 51
5 votes
Accepted

Preconditioner for scalar laplacian system

Preconditioning and iterative solvers are cool, but did you try to solve your problem with some kind of sparse direct solver? If not, try it first. State–of–the–art preconditioning techniques for ...
56th's user avatar
  • 901
5 votes
Accepted

Is it necessary to invert precondition matrix for iterative solver?

OK - so your original equation is $$Ax = b$$ Say you've come up with a good preconditioner for $A$, call this $M$. Also, say you have pre-computed an LU-decomposition for this $M$, i.e. $$M = L_m ...
GoHokies's user avatar
  • 2,206
5 votes

Is it necessary to invert precondition matrix for iterative solver?

Based on your comments, it looks like your main difficulty is how having an LU factorisation for a given matrix $M$ makes it easy to find a vector $\mathbf{y}$ such that $M\mathbf{y}=\mathbf{b}$ for a ...
origimbo's user avatar
  • 2,249
5 votes
Accepted

Right-preconditioning and fixed point linear iterations

Starting with $AM^{-1} \mathbf{y} = \mathbf{b}$, where $\mathbf{y} \equiv M \mathbf{x}$, we can manipulate to $\mathbf{y} - (I-AM^{-1})\mathbf{y} = \mathbf{b}$ Replacing one instance of $\mathbf{...
LedHead's user avatar
  • 1,253
5 votes
Accepted

Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?

There are several things to consider in this experiment: Why Matlab sparse direct might be "so fast": (for your particular test) In 2D (of course, problem-dependent), your matrix $A$ arising after ...
Anton Menshov's user avatar
  • 8,672
5 votes
Accepted

Are there any other better methods than block diagnoal and block upper triangular precondtioner for saddle point problems?

Your argument is almost correct, but not quite. You correctly state that the use of one AMG step for $B^{-1}$ and the identity matrix for $S^{-1}$ leads to a constant number of iterations, but that is ...
Wolfgang Bangerth's user avatar
5 votes
Accepted

What is the difference between Adittive Schwarz as a preprocessor and a solver?

By itself, Schwarz methods are stationary iterations just like Jacobi, Gauss-Seidel, or SOR. They converge to the solution, but often quite slowly. But, like any other stationary method, one iteration ...
Wolfgang Bangerth's user avatar
5 votes

Where can I find matrices and it's preconditioner for testing?

Generally, preconditioners are considered to be part of the solver, so they are not included in test matrix collections. In fact, preconditioners are rarely constructed as an explicit matrix, making ...
Neil Lindquist's user avatar
5 votes

What makes a good preconditioner when only a few approximate iterations are needed?

Edit there seem to be a few quantities that predict the difficulty based on how "flat" the spectrum is. Analysis below corresponds to the purity measure of spectrum flatness, but one could ...
Yaroslav Bulatov's user avatar
4 votes

Why does conjugate gradient work with this nonsymmetric preconditioner?

In short, orthogonalization of the Krylov vectors occurs with respect to the operator, but not with respect to the preconditioner. Alright, so say we want to solve $Ax=b$ with preconditioner $B$. ...
wyer33's user avatar
  • 767
4 votes

role of initial guess for iterative linear solver

It can be even harmful. In Liesen/Strakos Krylov subspace methods principles and analysis (Chapter 5.8.3) it is reported that a nonzero initial x0 makes a GMRes ...
Jan's user avatar
  • 3,418
4 votes
Accepted

Solution of linear system doesn't work, in parallel

ILU is not implemented for non-sequential matrices, see here.
Lilla's user avatar
  • 259
3 votes

role of initial guess for iterative linear solver

This answer is an addition to the one from Wolfgang Bangerth. It is certainly not worth to bother with the initial guess for the iterative linear solver if there is any work to be done: coding, ...
Anton Menshov's user avatar
  • 8,672
3 votes
Accepted

Preconditioner for the GMRES method in the Uzawa algorithm

Please check this paper by Benzi et al. They address this issue and give corresponding references on p. 45. Shortcut: for the Stokes problem $A = \text{diag}(A_{11},A_{11},\dots,A_{11})$ is just a ...
56th's user avatar
  • 901
3 votes

preconditioner for Laplace "without" boundary values

Here is at least an idea, whether it works is a different question. Let's say you sort unknowns so that you have the ones in the interior of the domain first, and then all those at the boundary. Then ...
Wolfgang Bangerth's user avatar
3 votes
Accepted

Incomplete Cholesky preconditioner for CG efficiency

Iterative solvers are (almost always) memory-bandwidth bound. So, how you access memory is very important. Modern computers work in cache lines, where a set of contiguous bytes will be fetched ...
Neil Lindquist's user avatar
3 votes

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

The computation in your update does most of the work towards a solution. You just need to note that $\frac{\varepsilon_1}{\varepsilon_2} \leq \frac{\max D_{ii}}{\min D_{ii}} = \kappa(D)$, and that $$ ...
Federico Poloni's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible