People who code: we want your input. Take the Survey

# Questions tagged [preconditioning]

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

100 questions
Filter by
Sorted by
Tagged with
2answers
89 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 ...
1answer
118 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 ...
0answers
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....
1answer
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,...
0answers
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'...
1answer
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-...
0answers
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 ...
0answers
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)|)$ ...
0answers
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 ...
1answer
188 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 ...
1answer
76 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 ...
0answers
95 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 ...
1answer
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, ...
1answer
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 ...
1answer
192 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) ...
2answers
329 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 ...
1answer
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 ...
1answer
101 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 ...
0answers
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 (...
1answer
215 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 ...
0answers
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, ...
0answers
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 ...
1answer
247 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 ...
1answer
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 ...
1answer
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 ...
1answer
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 ...
0answers
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 ...
1answer
257 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. ...
1answer
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 ...
0answers
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 ...
1answer
264 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, ...
1answer
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$ (...
0answers
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 ...
1answer
133 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 ...
1answer
595 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? ...
2answers
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. ...
0answers
287 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 ...
2answers
953 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 ...
0answers
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 ...
2answers
180 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., \...
2answers
903 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 ...
1answer
163 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$, ...
2answers
258 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\...
0answers
515 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 "...
1answer
458 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, ...
1answer
281 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 ...
1answer
196 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 ...
0answers
189 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 ...
0answers
77 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)...
1answer
174 views

### Difference between explicit and implicit preconditioning

What is the difference between an explicit and implicit preconditioner?