Questions tagged [preconditioning]
For questions regarding design and implementation of preconditioners for solving linear systems.
100
questions
0
votes
2answers
86 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 ...
2
votes
1answer
113 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 ...
3
votes
0answers
52 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....
-1
votes
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,...
2
votes
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'...
1
vote
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-...
1
vote
0answers
64 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 ...
2
votes
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)|)$ ...
0
votes
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 ...
5
votes
1answer
178 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 ...
0
votes
1answer
71 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 ...
3
votes
0answers
86 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 ...
3
votes
1answer
72 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, ...
1
vote
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 ...
3
votes
1answer
191 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) ...
3
votes
2answers
323 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 ...
6
votes
1answer
311 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 ...
1
vote
1answer
99 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 ...
7
votes
0answers
75 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 (...
3
votes
1answer
211 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 ...
1
vote
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, ...
8
votes
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 ...
2
votes
1answer
238 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 ...
0
votes
1answer
108 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 ...
1
vote
1answer
72 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
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 ...
3
votes
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 ...
2
votes
1answer
247 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.
...
-4
votes
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 ...
3
votes
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 ...
8
votes
1answer
257 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
173 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
111 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
130 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 ...
7
votes
1answer
551 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?
...
1
vote
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. ...
1
vote
0answers
280 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
2answers
894 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 ...
2
votes
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 ...
2
votes
2answers
177 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
872 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
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$, ...
4
votes
2answers
254 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
503 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
453 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, ...
3
votes
1answer
274 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
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 ...
5
votes
0answers
187 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 ...
2
votes
0answers
76 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
166 views
Difference between explicit and implicit preconditioning
What is the difference between an explicit and implicit preconditioner?
