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

learn more… | top users | synonyms

6
votes
1answer
270 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, ...
4
votes
1answer
65 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
103 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 ...
6
votes
0answers
67 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} :=& ...
0
votes
0answers
34 views

Constrained SVD/Lanczos given left/right matrices are banded

$A$ is a symmetric (known to be invertible) matrix of size $(N+p) \times (N+p)$ and $X$ is a rectangular matrix of size $(N+p) \times N$. The product $X^{T}AX$ is well-defined and non-singular. One ...
7
votes
1answer
150 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
113 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
100 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
72 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 & ...
4
votes
1answer
97 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
45 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
128 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
37 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: ...
4
votes
2answers
114 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
128 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
129 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
95 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
62 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
227 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
116 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
0answers
96 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
207 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 ...
0
votes
0answers
77 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 ...
7
votes
1answer
201 views

Why should I renormalize physical variables?

I am working with legacy physical codes and I develop new ones based on the output of them. They all use their own internal normalization of variables (for example all distances are divided by the ...
1
vote
1answer
98 views

Heuristic help with preconditioning large system ODEs

I'm looking for some general insight on preconditioning. In particular, relevant references/resources/comments would be greatly appreciated. Note, I have been through some of the literature, but am ...
4
votes
1answer
816 views

High quality flexible GMRES (FGMRES) implementation

What are the best FGMRES implementations in various languages/frameworks? In particular, are there any good quality Matlab implementations? I am referring to the variation of GMRES where a changing ...
11
votes
2answers
395 views

preconditioning a krylov method with another krylov method

In method like gmres or bicgstab it could be attractive to use another krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
1
vote
0answers
185 views

How to solve sparse linear systems using CPUs and GPUs?

There are several libraries to (iteratively) solve large sparse linear equation systems in parallel on a number of CPUs. Our parallel cluster also has attached powerful GPUs, but so far, I did not ...
11
votes
2answers
251 views

Do black-box preconditioners for matrix-free methods exist?

Jacobian-Free Newton-Krylov (JFNK) methods, and Krylov methods in general, can be very useful because they don't require explicit storage or construction of a matrix, only the results of matrix-vector ...
0
votes
1answer
648 views

Dual time stepping for fluid dynamics

I'm attempting to implement the Weiss and Smith preconditioner in an existing finite volume code and I am struggling with the idea of dual time stepping. My inner time steps are predictor-corrector, ...
13
votes
2answers
303 views

Is there any way to do “double preconditioning”

Question: Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$: $$A \approx B^TB$$ and $$A \approx C^TC,$$ where the inverses of the factors $B, ...
4
votes
1answer
91 views

What type of matrices is approximate inverse preconditioner $||I - AM||_F$ well suited for?

Take sparse approximate inverse preconditioner $M \approx A^{-1}$ given by solution of $$\underset{M \in S}{\mbox{min}} \; ||I - AM||_F,$$ where $S$ is a set of sparse matrices and $||.||_F$ is the ...
5
votes
3answers
266 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...
7
votes
1answer
515 views

Solving a large non-hermitian generalised eigenvalue problem from a linear stability analysis using SLEPc

I have a generalised matrix problem: $A x = \lambda B x$ from a spectral method on a linear stability analysis problem. My matrix B is diagonal and positive semi-definite. A is non-hermitian and ...
3
votes
1answer
212 views

Jacobi preconditioner not reducing condition number?

Let's say you have a normal matrix $A$, with diagonal entries $a_{ii} = d>0$. (No assumptions are made about the off-diagonal elements.) Then Jacobi preconditioning doesn't improve condition ...
10
votes
2answers
871 views

Which preconditioners (and solver) in PETSc for indefinite symmetric systems should I use?

My system is a symmetric FE problem with lagrange multipliers (e.g. incompressible Stokes' flow): \begin{pmatrix}A & B^T \\ B & C\end{pmatrix} where $C = 0$ is the typical case (I have even ...
4
votes
2answers
246 views

Existence of incomplete cholesky factorization

What is the current state of research on the existence of incomplete cholesky factorizations (in the context of preconditioning) for symmetric positive definite matrices? I wonder in particular ...
8
votes
1answer
382 views

Extracting diagonal of an approximately diagonal matrix when we don't know its entries

What is a good way to extract the diagonal from a symmetric matrix that is already almost diagonal, but where you don't have the matrix elements (only the ability to apply it to vectors)? Further ...
6
votes
1answer
342 views

Using algebraic multigrid for preconditioning convection-diffusion operators

I implemented a Navier Stokes based on FEM discretization and PETSc for solving the linear system of equations. To create an efficient solution procedure, I follow the paper "Efficient preconditioning ...
12
votes
1answer
349 views

What is the current state of polynomial preconditioners?

I wonder what has happened to polynomial preconditioners. I am interested in them, because they appear to be comparatively elegant from a mathematical perspective, but as far as I have read in surveys ...
11
votes
2answers
255 views

Efficient preconditioner for Augmented Lagrangian

I want to solve a non-linear problem with non-linear equality constrains and I'm using a augmented Lagrangian with a penalty regularization term that, as well known, spoils the condition number of my ...
7
votes
2answers
834 views

Taxonomy of ILU preconditioners

I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent. Surfing the ...
8
votes
2answers
537 views

How can I precondition a non-linear problem before linearization?

When I think of solving non-linear equations, I generally think of linearizing first, then applying a preconditioner to the linear matrix. The thought occurred to me that it might be possible to ...
5
votes
2answers
721 views

How does matrix scaling influence linear solvers?

For instance, in MUMPS there is option to scale matrix s.t. all rows/columns have the same norm. This claims to decrease condition number and improve numerical properties of the matrix: ...
4
votes
3answers
388 views

On Vanilla Preconditioners for solving dense $Ax=b$ iteratively

I am looking for preconditioners which don't assume anything about the matrix or its origins. I basically want to be able to type in the following in MATLAB and have quick solving time: ...
15
votes
1answer
629 views

Are there any open source inverse-based multilevel ILU implementations?

I am very impressed with the serial performance of multilevel inverse-based ILU preconditioners, particularly for heterogeneous Helmholtz, but I am surprised to not be able to find any open source ...
16
votes
3answers
842 views

What guidelines should I use when searching for good preconditioning methods for a specific problem?

For the solution of large linear systems $Ax=b$ using iterative methods, it is often of interest to introduce preconditioning, e.g. solve instead $M^{-1}(Ax=b)$, where $M$ is here used for ...
11
votes
5answers
2k views

What is the advantage of multigrid over domain decomposition preconditioners, and vice versa?

This is mostly aimed for elliptic PDEs over convex domains, so that I can get a good overview of the two methods.
14
votes
2answers
5k views

Why is my iterative linear solver not converging?

What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...
3
votes
1answer
78 views

Applicability of combinatorial and support preconditioner

There are several correspondences between matrices and graphs, e.g., each matrix is the adjacancy matrix of a weighted graph. The terms support preconditioner or combinatorial preconditioner refer to ...