Questions tagged [preconditioning]
For questions regarding design and implementation of preconditioners for solving linear systems.
2
votes
1answer
55 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
votes
0answers
61 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 ...
1
vote
1answer
87 views
Multigrid preconditioner for conjugate gradient methods
When solving $A*x=b$ using preconditioned conjugate gradient methods one has to solve $z=K^{-1}*r$ for the preconditioning where $K$ is the preconditioner of $A$ and $r$ is the residual vector.
...
0
votes
0answers
22 views
Preconditioning grad(ln(u)) term
I am trying to solve a nonlinear diffusion-type problem using the finite element method which has the following terms:
$-\nabla\cdot k_1\nabla u - \nabla\cdot k_2\nabla\mathrm{ln}(u) = 0$ in $\Omega$
...
-4
votes
1answer
85 views
what is Sherman-Morrison formula
Can someone please explain what is the Sherman-Morrison formula and it's specialities when it comes to matrix calculations? I'm a little bit confused on understanding how the preconditioning works ...
3
votes
0answers
65 views
Element Preconditioner
Im just working on a preconditioner for the linear equation system $Ax = b$ arising in FEM for elliptic PDE. $A$ is a s.p.d Matrix with real valued entries. I read something about the element by ...
8
votes
0answers
105 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, ...
3
votes
1answer
135 views
Efficient implementation of preconditioners for iterative solvers
I am struggling a bit with the concept of preconditioners for iterative solvers and how to implement them efficiently. The literature mostly provides methods to create a preconditioner matrix $M$ (...
4
votes
0answers
52 views
Preconditioned residual converges, but true residual doesn't
I'm using Albany w/ Trilinos to solve an elasticity problem with thermal expansion mismatch. I'm using block GMRES with MueLu preconditioning. It works for problem size of several million dofs, but ...
6
votes
1answer
75 views
Eigenvalue problems with extremely small gaps
I'm interested in numerically diagonalizing a class of structured, symmetric eigenvalue problems with potentially extremely small eigenvalue gaps. The question I have is how to design a numerically ...
6
votes
1answer
249 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?
...
0
votes
1answer
141 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. ...
1
vote
0answers
166 views
Why does PETSc take unexpectedly long to set up its KSP solver with a custom preconditioner? [closed]
I am attempting to solve a large system, $\bf{Ax} = \bf{b}$ with the help of PETSc. Due to the size of the problem, I'm using a matrix-free approach, where $\bf{A}$ is just a shell. I'm also providing ...
2
votes
0answers
49 views
Scaling for a nonsymmetric eigenvalue problem
I have an eigenvalue problem emerging from the internal vibro-acoustic coupling.
The eigenvalue problem is nonsymmetric but it was proven in literature that it results in real eigenvalues and ...
2
votes
2answers
133 views
Preconditioner for scalar laplacian system
Suppose that I have a large (on the order of 10^6 unknowns) 3D scalar Poisson system which I would like to precondition. The boundary conditions have been treated so that the system is SPD. I.e.,
$$\...
1
vote
2answers
416 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 ...
1
vote
1answer
159 views
Computing preconditioner for a non-linear conjugate gradient implementation
Consider the following steps for the $i$-th non-linear conjugate gradient iteration, in the context of 3D electromagnetic inversion, and as discussed in (Newman and Boggs, 2004):
(1) set $i = 1$, ...
4
votes
2answers
185 views
Preconditioner for the GMRES method in the Uzawa algorithm
I'm trying to solve
\begin{equation}\left\{
\begin{split}
\frac{\partial u}{\partial t}+(u\cdot\nabla)u-\nu\Delta u+\frac1\rho\nabla p&=f\;\;\;\text{in }\Lambda\\
u&=0\;\;\;\text{on }\partial\...
1
vote
0answers
233 views
How to use “fill_factor” in spilu (scipy) [closed]
I am using spilu (incomplete LU decomposition for sparse matrix) in scipy:
https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.linalg.spilu.html
However there is an option call "...
2
votes
1answer
245 views
Preconditioner for dense matrix “with diagonal predominance”
For a CFD panel-based potential method, I'm trying to reduce the time to solve the linear system. The matrix has the larger values on the diagonal, since the influence of a panel on itself is maximum, ...
4
votes
1answer
211 views
SLEPc eigensolvers take long time to converge for large sparse symmetric matrices
I am leveraging the SLEPc library for solving the first $k$ (where $k = 3$ or $4$) eigenvalues and their corresponding vectors for a matrix of size 200,000. The matrix is sparse and symmetric. I ...
0
votes
1answer
149 views
Iterative methods to solve linear system in 3D FEM
I implemented a FEM solver in MATLAB for Poisson's equation in 3D, using hexahedron and sparse matrix for the Laplacian. I was using the backslash but now I have to use a few iterative methods (GMRES ...
5
votes
0answers
129 views
Preconditioning technique for large sparse non-hermitian matrix
I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
1
vote
0answers
58 views
Preconditioners and discrete Lagrange multipliers
There is a huge literature on efficient preconditioners for saddle-point problems. In computational physics, the case where the Lagrange multipliers enjoy a weak formulation (say, the Stokes equations)...
1
vote
1answer
127 views
Difference between explicit and implicit preconditioning
What is the difference between an explicit and implicit preconditioner?
2
votes
0answers
40 views
Preconditioning matrix with known spectrum
Assume I know all eigenvalues of a matrix $A$ fall into a certain set $\Omega \subset \mathbb{C}$. Is there any way I can exploit this knowledge to design a preconditioner for $A$?
Some further ...
3
votes
2answers
434 views
Python environments for AMG and Gauss Seidel as solvers instead of preconditioners
I am working on block preconditioning and seemingly it is common to write customised Krylov solvers for them. Within each solver, the individual block linear system with preconditioners are ...
1
vote
1answer
361 views
Preconditioning of two step iteration for dense matrices
I would like to solve a dense linear system the form in python
$$
L\left(\boldsymbol{x}\right):=\left[\gamma^+\left[\boldsymbol{A}+\frac{1}{2}\boldsymbol{B}^{-1}\right]
+\gamma^-\left[\boldsymbol{A}-\...
7
votes
1answer
372 views
“Cookbook” about iterative linear solvers and preconditioners
I'm using a lot of linear solvers and preconditioners, but mostly, they are magical black boxes to me. Since I'll also have to implement some of them in future, I would like to learn a bit more, ...
6
votes
3answers
284 views
role of initial guess for iterative linear solver
Suppose we use a preconditioned iterative solver for a linear system. If the initial state for the solver can be chosen very close to the exact solution - does this reduce requirements for the ...
3
votes
1answer
1k views
Solving linear systems with ill-conditioned matrices
As per suggestions of the people from MathOverflow, I'm reposting my question here:
I'm currently trying to solve a linear system $Ax = B$, where the matrix $A$ is ill conditioned (i.e. nearly ...
9
votes
2answers
250 views
Why does conjugate gradient work with this nonsymmetric preconditioner?
In this previous thread the following multiplicative way to combine symmetric preconditioners $P_1$ and $P_2$ for the symmetric system $Ax=b$ was suggested:
\begin{align}
P_\text{combo}^{-1} :=& ...
7
votes
1answer
425 views
Which preconditioning for large linear elasticity problem?
The problem I want to solve is the displacement formulation of the linear elasticity :
$$
\nabla \cdot \sigma = 0 \quad \text{in} \quad \Omega \\
\sigma = \lambda ( \nabla \cdot u ) I + \mu (\nabla \...
5
votes
2answers
124 views
Does this partial eigen-expansion have a name?
This question is a follow-up to this one.
Let $A\in \mathbb{R}^{n\times n}$ be large, sparse, symmetric and positive definite. Suppose for I already know $m<n$ eigenpairs of $A$, corresponding to ...
4
votes
1answer
176 views
Best solver/preconditioner for least-squares finite element method
I have seen a lot of literature, lecture videos, etc. on solvers/preconditioners for non-symmetric and/or indefinite systems. However, now I want to solve the mixed poisson/Darcy equation using the ...
2
votes
0answers
138 views
preconditioned Uzawa method with Petsc
I am trying to improve the resolution of a Stokes problem (P2/P1 on unstructured mesh) defined by the matrix $M$:
$M=
\begin{pmatrix}
A_u & 0 & B_u \\
0 & A_v & B_v\\
B_u^T & B_v^...
4
votes
1answer
173 views
Choosing preconditioner for unsymmetric pressure-velocity coupled system
I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
1
vote
0answers
64 views
Non-overlaping Domain decomposition - assemble of Laplacian
I am dealing with following 2-dimensional problem in the unit square domain $S_2$
$$- \Delta u (x,y) = f \ \text{in} \ S_2, \hspace{1.5cm} u(x,y) = 0 \ \text{on} \ \partial S_2$$
where $f$ is ...
9
votes
1answer
143 views
What iterative method can effectively solve a linear system with this kind of spectrum
I have a linear system with matrix which eigenvalues are uniformly distributed on the unit circle like this:
Is it possible to solve this kind of system effectively by iterative method, maybe with ...
1
vote
0answers
45 views
How to compute the inner system(like schur complement) effeciently
i got a factorization of $A$ like $A=D+F*H$, where $D$ is a block diagonal matrix and $F,H$ are low-rank matrices.
I consider to use the Woodbury formula to construct a solver:
$A^{-1}=D^{-1}(I-F(I+...
5
votes
2answers
258 views
Preconditioning symmetric Schur complement
Consider a $2\times 2$ block matrix and a linear system of equations associated to it:
\begin{equation}
\begin{pmatrix} - A & B \\ B^t & C \end{pmatrix}
\begin{pmatrix} x \\ y \end{pmatrix}
...
2
votes
1answer
193 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 ...
1
vote
1answer
210 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 shared-memory system with OpenMP. In addition, I want to precondition ...
0
votes
1answer
393 views
Avoid arithmetic overflow in matrix multiplication
I am solving the following matrix equation for $\mathbf{x}$:
$$(J^{\mathbf{T}}J)\mathbf{x}=J^{\mathbf{T}}\mathbf{r}$$
$J$ is $m\times n$ matrix
$\mathbf{x}$ is vector of size $n$
$\mathbf{r}$ is ...
1
vote
0answers
83 views
Block preconditioners and condition number
I am working with block Jacobi like preconditioners which are very cheap for my problem. But I could not find much about the dynamics of basic preconditioners (block Jacobi, Gauss-Seidel, ILU etc). ...
2
votes
1answer
326 views
Construct a preconditioner for the linear system $Ax = b$ from a different matrix
When I use PETSc to solve my linear systems, I always use the subroutine
PetscErrorCode KSPSetOperators(KSP ksp,Mat Amat,Mat Pmat)
where ...
5
votes
1answer
133 views
Effect of subdomain topologies on overlapping additive Schwarz?
Is there a reference on the effect of subdomain topology on performance of the overlapping additive Schwarz method for (high order) finite elements? For example, taking subdomains to be vertex ...
9
votes
1answer
138 views
Guidelines for nested preconditioners
Consider the situation where you want to solve a linear system using a preconditioned Krylov method, but applying the preconditioner itself involves solving an auxiliary system, which is done with ...
3
votes
1answer
280 views
Designing a preconditioner for a very Ill-conditionned matrix
I am a physicist with limited numerical methods knowledge and I am trying to speed up the inversion of a very ill-conditioned problem ($rcond>10^{30}$). The same sparse square matrix is used ...
1
vote
0answers
85 views
Eigenvalue analysis of preconditioned partial differential operator
today, I encountered a confused problem by accident, but I have no ideas to deal with it fully. The question can be described as follows: for example, when we need to use FDM/FEM to discrete the ...
