Questions tagged [preconditioning]
For questions regarding design and implementation of preconditioners for solving linear systems.
112
questions
8
votes
1
answer
189
views
What makes a good preconditioner when only a few approximate iterations are needed?
For deterministic solver of $Xw=y$, one recommendation is to pick $P$ such that $P^{-1}X$ has a low condition number. However, this condition only really matters when you want to reduce initial error ...
- 1,422
2
votes
2
answers
728
views
Why does this preconditioner effectively reduce the condition number of a random SPD matrix?
Consider some randomly generated matrix $B\in\mathbb{R}^{100\times100}$ and let $A:=BB^{\top}$
On MATLAB I computed the condition number of $A$, I obtained a value of $2.8377\mathrm{e}+04$
However if ...
- 1,175
1
vote
2
answers
1k
views
Is it necessary to invert precondition matrix for iterative solver?
I was reading these slides about preconditioners. I believe I grasp the idea of how they work but there is something that is still not making sense.
If we have the system $Ax=b$ and use a ...
3
votes
0
answers
28
views
Reference for preconditioning nonlinear conjugate gradient with LU decomposition of jacobian
When solving non-linear systems of equations, @Arnold Neumaier suggested in How can I precondition a non-linear problem before linearization? to use an approximate LU decomposition of an approximate ...
- 31
2
votes
1
answer
257
views
Best preconditioner for mixed-poisson problem (RT0 elements)
For a very large mixed-poisson problem with lowest order Raviart-Thomas elements (RT0), I plan on using an iterative solver. However, this kind of problem is not positive-definite (saddle point ...
- 51.3k
13
votes
2
answers
2k
views
Which preconditioners (and solver) in PETSc for indefinite symmetric systems should I use?
My system is a symmetric FE problem with lagrange multipliers (e.g. incompressible Stokes' flow):
\begin{pmatrix}A & B^T \\ B & C\end{pmatrix}
where $C = 0$ is the typical case (I have even ...
- 51.3k
10
votes
2
answers
567
views
Extracting diagonal of an approximately diagonal matrix when we don't know its entries
What is a good way to extract the diagonal from a symmetric matrix that is already almost diagonal, but where you don't have the matrix elements (only the ability to apply it to vectors)?
Further ...
- 505
7
votes
1
answer
1k
views
How to directly compute the inverse of an ill-conditioned dense matrix
I know that it is generally a bad idea to compute the inverse matrix directly. However, if it is necessary to compute the inverse of an ill-conditioned invertible dense matrix, then what can I try?
...
- 8,452
2
votes
1
answer
66
views
ICCG negative residual products $r^TM^{-1}r$
I have a linear system $Ax=b$ resulting from a finite element discretization of the Poisson equation. I am applying an IC0 (incomplete Cholesky ($LDL^T$) with the same sparsity as the original matrix) ...
- 369
0
votes
2
answers
87
views
Where can I find matrices and it's preconditioner for testing?
I want to find some kinds of matrices for testing my code such as GMRES , MINRES and so on. But I can't find some testing matrices and corresponding preconditioner to verify my program.
I know some ...
- 10.8k
1
vote
1
answer
287
views
OpenMP threaded nonlinear solver for complex numbers
Problem:
I have translated Jacobian-Free Newton-Krylov solver written by
C. T. Kelley to Fortran and now want to parallelize it on a shared-memory system with OpenMP. In addition, I want to ...
- 8,452
1
vote
0
answers
42
views
Hessian-free preconditioner for non linear least squares
I am solving a nonlinear least squares problem using Gauss Newton method. Due to the large dimension of the problem, I use the Hessian-free approach. As a linear solver I use either MINRES or CG. To ...
3
votes
1
answer
194
views
Incomplete Cholesky preconditioner for CG efficiency
I am currently solving the harmonic equation using a P1 FEM discretisation. The resulting matrix $A$ is SPD and fairly sparse so I use a preconditioned conjugate gradients (CG) solver to find a ...
- 369
3
votes
1
answer
418
views
When do not use preconditioners for sparse linear system of equations?
I'm implementing a solver of Finite Element Method, and to solve the linear system of equations I'm using gmres from MKL of Intel. Exists the option with and without a preconditioning. In what case it ...
- 8,452
0
votes
0
answers
45
views
Normalizing the right-hand side in Jacobi-preconditioned conjugate gradients
I have been reading the following paper: CG versus MINRES: An empirical comparison.
In it a conjugate gradient solver is applied to a system matrix $A$ Jacobi-preconditioned on both sides. ...
- 369
1
vote
1
answer
109
views
What is the difference between Adittive Schwarz as a preprocessor and a solver?
As we all know, the Additive Schwarz approach can be used as either solver or preconditioner, however, my question is, what is the difference between the two? In other words, how to use AS as solver, ...
- 981
3
votes
1
answer
231
views
Preconditioning vs. regularization
I used to be more of a numerical linear algebra and computational science person, but recently, I've crossed into stats and machine learning.
For this discussion, let's focus on matrices that are not ...
CommunityBot
- 1
3
votes
1
answer
131
views
Preconditioning a least-squares problem?
I need to solve an equation system
$$
\begin{pmatrix}
A \\
I
\end{pmatrix}
x
=
\begin{pmatrix}
b_0\\b_1
\end{pmatrix}
$$
in the least-squares sense. Let's assume $I$ is the $n$-by-$n$ identity matrix, ...
- 9,055
1
vote
3
answers
159
views
preconditioner for Laplace "without" boundary values
I'm looking at solving systems with the FEM discretization
$$
-\int_\Omega (\Delta u) v = \int_\Omega \nabla u \cdot \nabla v - \int_\Gamma (n\cdot\nabla u) v.
$$
without applying Dirichlet- or ...
- 3,058
5
votes
1
answer
280
views
Non-negative least squares with very small numbers
(I have asked this question on StackOverflow previously but it has been pointed to me that CSSE or MSE could be more appropriate)
I have to solve a constrained optimization problem of the following ...
CommunityBot
- 1
2
votes
0
answers
105
views
Confusion about preconditioner for incompressible Navier-Stokes equation with implicit-explicit method
Consider the time-dependent Navier-Stokes equation
$$u_t + (u \cdot \nabla) u - \Delta u + \nabla p = f$$
$$\operatorname{div}(u)=0$$
Looking at deal.ii tutorials, I've notice that there are ...
- 289
1
vote
2
answers
203
views
How to verify solution to pre-conditioned linear systems solver?
I am solving Ax=b. A has a very large condition number (> O(10^10))
I am using the conjugate gradients method with point jacobi pre-conditioning. I obtained a solution 'x' that "looks" reasonable. ...
- 10.8k
3
votes
0
answers
84
views
What is this QR-factorization-based preconditioning called?
I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization....
- 203
-1
votes
1
answer
41
views
Automatic selection of the SLE solver and preconditioner during simulation
To simulate the physical process necessary to solve the arising systems of linear algebraic equations. The SLE matrix has a highly sparse form. There are a couple dozen non-zero elements in the string,...
- 51.3k
2
votes
0
answers
42
views
"black box" preconditioner for shifted linear systems?
Does anyone know of any strategies for creating a preconditioner $P^{-1}_\sigma \approx (A+\sigma I)^{-1}$ given a preconditioner $P^{-1} \approx A^{-1}$, preferably such that the precomputation doesn'...
- 51.3k
1
vote
1
answer
88
views
preconditioner for $u''(x)=\sin(x)$
I am interested in finding preconditioner to solve the problem for one dimensional problem $u''(x)=\sin(x), u(0)=u(1)=0$ using Dirichlet-Neumann method.
The preconditioner $M$ coming from Dirichlet-...
- 51.3k
1
vote
0
answers
124
views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
- 11
2
votes
0
answers
71
views
Does incomplete LU preconditioning improve the asymptotic scaling of Krylov subspace methods?
It is well known that unpreconditioned Krylov subspace methods applied to the finite-difference-discretised Poisson equation with $n$ grid points per direction require $O(n \, |\log(\varepsilon)|)$ ...
- 405
0
votes
0
answers
70
views
Preconditioning the $[1 \quad-2 \quad 1]$ Finite Difference matrix
Let $A$ be the well known tridiagonal matrix coming from the 1D Finite difference discretization of the Laplacian, with stencil $\frac{[1 \quad-2 \quad 1]}{h^2}$.
The system $Ax = b$ is very large, so ...
- 289
16
votes
2
answers
887
views
Preconditioning a Krylov method with another Krylov method
In methods like gmres or bicgstab it could be attractive to use another Krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
- 8,452
0
votes
1
answer
108
views
Library to solve dense linear system with GMRES
I have a fortran 90 code and I want to solve a dense linear system with GMRES. I would prefer the restarted GMRES with preconditioning. Is there some library that you know of that I could use? Now I ...
- 1,902
7
votes
1
answer
653
views
Jacobi preconditioner not reducing condition number?
Let's say you have a general matrix $A$, with diagonal entries $a_{ii} = d>0$. (No assumptions are made about the off-diagonal elements.) Then Jacobi preconditioning doesn't improve condition ...
- 8,452
8
votes
1
answer
327
views
How to find a good preconditioner to the system $(A^T A + \lambda I) x = A^T b$?
The system in the title has a damper factor $\lambda > 0$ and the matrix $A$ is sparse and rectangular, with a structure I can exploit to solve matrix vector products very fast. My current solver, ...
- 2,311
3
votes
0
answers
139
views
Solving saddle point problem having non-invertible top-left block with a PETSc nested matrix
My system is a symmetric FE problem with lagrange multipliers:
$Z=\begin{pmatrix}A & C^T \\ C & 0\end{pmatrix}$
The matrix $A$ is positive semi-definite, non-invertible. The whole matrix is ...
- 151
3
votes
1
answer
91
views
Are there any other better methods than block diagnoal and block upper triangular precondtioner for saddle point problems?
For stokes problems,
$$
-\Delta \vec{u} + \nabla p =\vec{f},\qquad \nabla . \vec{u} = 0;
$$
with appropriate boundary conditions which guarantee there is a unique solution.
Using FDM or FEM, ...
- 51.3k
1
vote
1
answer
53
views
Accelerating Conjugate Gradients fitting for small localized kernel (like cubic B-spline)
Question:
Is there some pre-conditioner for Conjugate-Gradient (CG) cheap enough, that it is worth using even if my operator is very local (i.e. already has a low number of non-zero elements), as it ...
- 8,452
2
votes
2
answers
1k
views
Correct use of scipy's sparse.linalg.spilu
I'm attempting to use scipy's spilu routine as a preconditioner and I'm finding bad performance for my application (solving a global linear system arising from a DG ...
- 8,452
3
votes
1
answer
228
views
Why do many people use FDM method to solve Stokes equations, i.e., saddle point matrix?
For numerical methods of the Stokes equations, with appropriate boundary:
$$-\nabla^{2} \vec{u}+\nabla p=\overrightarrow{0}$$
$$\nabla \cdot \vec{u}=0$$
one may use FDM (finite difference method) ...
- 8,452
3
votes
2
answers
464
views
Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?
Recently, I have met a question that
a saying goes that for large linear system: iterative methods are required because of memory problem of direct methods.
But when I implement some experiments ...
- 971
6
votes
1
answer
334
views
Iterative linear solver for "ugly" saddle point system
I am a graduate student majoring scientific computing. The numeric model I made caused a very ugly-looking saddle-point linear system. It is not symmetric at all and I will attach the sparsity pattern ...
- 8,452
1
vote
1
answer
145
views
Iterative solution of ill-conditioned matrix systems
I want to solve a matrix system of the form $Ax=b$ where $A$ is ill-conditioned. The matrix system comes from a structural simulation problem which was discretized using finite elements. I do not have ...
- 1,902
8
votes
0
answers
130
views
Why not use the preconditioned residual as termination criterion for preconditioned CG?
I have a Poisson equation with wildly varying material parameters (1 .. 1000), wildly varying element sizes (5 nm .. 100 um) and some quite anisotropic (tetrahedral) elements (100 nm x 100 um). I use (...
- 2,131
1
vote
0
answers
70
views
Kinetic preconditioning
Publication arXiv:0804.2583 describes a method for doing self-consistent iteration without having to diagonalize the Hamiltonian operator at every step.
IX. PRECONDITIONING
As already mentioned, ...
CommunityBot
- 1
3
votes
1
answer
264
views
Optimality of block-Jacobi preconditioner
For a dense $N \times N$ matrix $A$, is the block-Jacobi preconditioner comprising the inverse of the diagonal blocks of $A$ the optimal block-diagonal preconditioner? Could there exist another matrix ...
- 8,452
8
votes
0
answers
100
views
How to construct an effective preconditioner for this particular problem
A quick introduction to my problem
I am currently developing a method for simulation of water waves in three dimensions based on potential flow theory. The computational bottleneck of the method is ...
- 8,452
2
votes
1
answer
343
views
Re-using LU factorization within iterative (?) setup for a sum of two matrices
So, I would love to make at least some use of my preexisting data, no matter how small, and just out of ideas. Maybe I am just a prisoner of a Kahneman-like theatre-ticket paradox, and don't know ...
- 8,452
0
votes
1
answer
157
views
PCJACOBI works but the default PCBJACOBI failed in PETSc
I am using PETSc and libmesh to solve a simple linear elastic problem with quite complicated geometry, using linear tetrahedral elements. I am always using the KSP CG as the solver.
I noticed that ...
- 8,452
1
vote
1
answer
117
views
Simplest way to precondition Uzawa iteration
I have a diffusion problem with an internal circular dirichlet constraint and a side condition which shall enforce a certain global volume integral.
$\nabla(D \nabla u(x)) = 0$
outer boundary ...
2
votes
1
answer
73
views
Right-preconditioning and fixed point linear iterations
Given a linear system $A\textbf{x}=\textbf{b}$, we can express it into the easier-to-solve right-preconditioned form:
$$ AM^{-1}\textbf{y}=\textbf{b}, \quad \textbf{y}= M\textbf{x} $$
On the other ...
- 2,116
3
votes
0
answers
78
views
Numerical analysis, pivoting and incomplete LU decomposition
When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
- 31