# Questions tagged [preconditioning]

For questions regarding design and implementation of preconditioners for solving linear systems.

100 questions
Filter by
Sorted by
Tagged with
90 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 ...
120 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 ...
54 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....
32 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,...
37 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'...
85 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-...
66 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 ...
65 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)|)$ ...
61 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 ...
193 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 ...
78 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 ...
96 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 ...
74 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, ...
44 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 ...
193 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) ...
330 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 ...
313 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 ...
102 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 ...
76 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 (...
216 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 ...
60 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, ...
88 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 ...
248 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 ...
111 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 ...
80 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 ...
69 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 ...
71 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 ...
258 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. ...
125 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 ...
76 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 ...
265 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, ...
178 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$ (...
113 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 ...
134 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 ...
598 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? ...
197 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. ...
291 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 ...
961 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 ...
57 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 ...
182 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., \...
907 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 ...
164 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$, ...
258 views

### Preconditioner for the GMRES method in the Uzawa algorithm

I'm trying to solve \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\...
516 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 "...
459 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, ...
282 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 ...
197 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 ...
190 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 ...