Skip to main content

Questions tagged [preconditioning]

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

Filter by
Sorted by
Tagged with
4 votes
0 answers
86 views

Computational efficiency of Galerkin projection in AMG

I have been using recently AMG as preconditioner for CG with several meshes for simple elliptic problems discretised with linear elements on "complicated" three dimensional geometries and I ...
FEGirl's user avatar
  • 405
3 votes
0 answers
63 views

Is AMG supposed to work with discontinuous Galerkin discretizations?

As the question says, are algebraic multigrid methods well suited to be used as preconditioners for problems discretised with Discontinuous Galerkin methods (say $p=1$)? I've always used AMG (actually,...
FEGirl's user avatar
  • 405
0 votes
0 answers
109 views

Is there a fast matrix-free inverse power iteration?

Problem: I want to solve the eigenvalue problem $$x=Ax$$ to the eigenvalue $1$ for a large matrix (roughly $N^3\times N^3$ and $N$ ranges from 10 to 100) where $A$ is stochastic (i.e. all entries are ...
Diplodokus's user avatar
2 votes
0 answers
95 views

Iterative solvers for problems in solid and structural mechanics

I am looking for comprehensive literature (papers, books, reports etc..) on iterative solvers for solid and structural mechanics problems to understand the best iterative solvers and preconditioners ...
Chenna K's user avatar
  • 944
0 votes
0 answers
39 views

Flexible Conjugate Residual

If we want to use variable preconditioning in Conjugate Gradient, we can replace the Fletcher–Reeves by the Polak–Ribière formula (https://en.wikipedia.org/wiki/Conjugate_gradient_method#...
GS101's user avatar
  • 21
1 vote
0 answers
71 views

Bachelor thesis going out of hand, need help [closed]

I am currently working on my bachelor thesis, which aims to enhance the multigrid preconditioned conjugate gradient algorithm proposed by Tatebe in 1993 using Deep Learning. Currently, I am ...
Glaand's user avatar
  • 11
0 votes
0 answers
58 views

how to implement ilu preconditioner for lsqr in python?

I am solving a least squares problem. Using lsqr is relatively slow. Is there a way to add a right preconditioner for lsqr? https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg....
Alvin's user avatar
  • 11
3 votes
0 answers
47 views

Preconditioned GMRES for nearly diagonalizable systems

I have been working with a matrix $A$ and preconditioner $P\approx A^{-1}$ that I've then applied GMRES to the (left) preconditioned linear system \begin{equation} P^{-1}Ax=P^{-1}b \end{equation} $P^{-...
Tucker's user avatar
  • 189
3 votes
2 answers
186 views

what preconditioner for incompressible hyperelasticity in 3d (similar to stokes equation?)?

I am working on modeling incompressible elasticity at finite strains. $$ \mathrm{Div} \boldsymbol P = \boldsymbol 0, \quad \boldsymbol X \in \Omega_0 \subset \mathbb R^3, \\ J = 1, \qquad \boldsymbol ...
Simon's user avatar
  • 175
4 votes
0 answers
130 views

How is the Alternating Schwarz Method used as a Preconditioner to a Krylov Method?

I am reading "Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations" (Smith 1996), and I am confused as to how the below Alternating Schwarz algorithm ...
Jared Frazier's user avatar
1 vote
0 answers
66 views

preconditioning least square in python?

For a nonsymmetric matrix, we can solve { A^T @ A x = A^T b } by lsqr or cgls or something else. Usually it will be slow, so we need a preconditioner either ilu, multigrid or something else. Is there ...
Alvin's user avatar
  • 11
1 vote
0 answers
48 views

Interpreting iterative smoothers and solvers as krylov preconditioners

Various literature and library implementations like petsc use preconditioners based on simple smoothers that themselves could be used the solve the systems directly. e.g. say I have a function ...
Aurelius's user avatar
  • 2,375
1 vote
0 answers
49 views

What is the current state of preconditioning highly heterogeneous equations? Where do I start?

Consider the simple standard Laplacian in 2D or 3D: $$\nabla (\alpha \nabla u) =f $$ with $\alpha$ being a scalar. $\alpha$ can take values that can vary largely between 1e-8 and 1 throughout the ...
CuteCompute's user avatar
6 votes
1 answer
351 views

Creating a preconditioner for conjugate gradient with a known approximate solution

I am working on solving Poisson's eq. $\Delta u = -f$ using conjugate gradient method. I am using scipy's linalg.cg function. In this problem, the source function $f$ changes slightly in each ...
Omer Paz's user avatar
2 votes
1 answer
175 views

Solution of linear system doesn't work, in parallel

I'm solving $Ax = b$ with PETSc, $A$ sparse and asymmetric. I'm using BCGS or FGMRES or TFQMR as a solver, and ILU as a preconditioner. When I use 1 core, everything works as expected. But with 8 ...
Lilla's user avatar
  • 259
0 votes
1 answer
80 views

How to combine multigrid preconditioner with jacobi preconditioner?

I have not found any relevant information in the literature on the following rather simple problem: How to combine (geometric) multigrid preconditioned conjugate gradient (MGPCG) with an additional ...
zx-81's user avatar
  • 1
1 vote
0 answers
81 views

Implementations of the Eisenstat-trick for SSOR

Where can I find a source code for the SSOR method with Eisenstat's trick? The original paper includes pseudo code but also seems to have minor typos. For that reason, I would be very happy to see an ...
shuhalo's user avatar
  • 3,680
4 votes
0 answers
91 views

Can you left-precondition least squares?

Suppose I want to solve an overdetermined linear least squares problem $$ x = \operatorname*{argmin}_{x\in\mathbb{R}^n} \| Ax - b\|^2 $$ where $A \in \mathbb{R}^{m\times n}$ has full column rank. I ...
eepperly16's user avatar
1 vote
1 answer
73 views

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

In passing I was told by someone that $K^{\prime}\in\mathbb{R}^{n\times n}$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $K$, where $K$ is ...
Tucker's user avatar
  • 189
3 votes
3 answers
177 views

How to find the optimal SSOR parameter

The symmetric successive overrelaxation method features the iteration matrix $$P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+U\right)$$ Either as a stationary ...
shuhalo's user avatar
  • 3,680
11 votes
2 answers
336 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 ...
Yaroslav Bulatov's user avatar
3 votes
2 answers
923 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 ...
UserX's user avatar
  • 133
3 votes
0 answers
37 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 ...
NaHenn's user avatar
  • 31
0 votes
2 answers
150 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 ...
Robert's user avatar
  • 3
1 vote
0 answers
59 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 ...
Aleksandr Borisov's user avatar
2 votes
1 answer
80 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) ...
lightxbulb's user avatar
  • 2,197
3 votes
1 answer
602 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 ...
lightxbulb's user avatar
  • 2,197
3 votes
1 answer
653 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 ...
yemino's user avatar
  • 515
1 vote
1 answer
180 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, ...
zhanghaoyuan's user avatar
3 votes
1 answer
222 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, ...
Nico Schlömer's user avatar
2 votes
0 answers
148 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 ...
Vefhug's user avatar
  • 309
1 vote
3 answers
207 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 ...
Nico Schlömer's user avatar
3 votes
1 answer
503 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 ...
anonuser01's user avatar
3 votes
0 answers
163 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....
J.Galt's user avatar
  • 203
-1 votes
1 answer
45 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,...
user37899's user avatar
2 votes
0 answers
47 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'...
deasmhumnha's user avatar
1 vote
1 answer
92 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-...
420's user avatar
  • 41
1 vote
0 answers
152 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 ...
randombeaver's user avatar
2 votes
0 answers
73 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)|)$ ...
gTcV's user avatar
  • 445
0 votes
0 answers
100 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 ...
Vefhug's user avatar
  • 309
5 votes
1 answer
382 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 ...
Nicola's user avatar
  • 51
0 votes
1 answer
220 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 ...
Riri's user avatar
  • 43
3 votes
0 answers
175 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 ...
janou195's user avatar
  • 161
3 votes
1 answer
122 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, ...
Happy's user avatar
  • 971
1 vote
1 answer
66 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 ...
Prokop Hapala's user avatar
2 votes
1 answer
270 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) ...
Happy's user avatar
  • 971
3 votes
2 answers
748 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 ...
Happy's user avatar
  • 971
6 votes
1 answer
387 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 ...
Hoarsehinghing's user avatar
1 vote
1 answer
274 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 ...
vydesaster's user avatar
8 votes
0 answers
236 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 (...
Thomas Klimpel's user avatar