Questions tagged [krylov-method]
Referring to Krylov Subspaces and the methods of solutions to linear systems of equations which exploit these spaces.
50
questions
4
votes
0answers
29 views
Implementation of Lanczos method that returns tridiagonal matrix
The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
0
votes
0answers
32 views
Why does GMRES converge much slower for large Dirichlet boundary conditions?
I'm trying to numerically solve a simple Laplace equation in 2D, with a nonlinear source term:
$\nabla^2 u = u^2$
with boundary conditions as $u=0$ everywhere except for $y=1$ where $u=u_0$. I'm ...
1
vote
1answer
97 views
Solving nonlinear PDE with finite difference based on Newton-Krylov
I am now working on solving MHD equations with finite difference method, which include nonlinear equations:
$$
\frac{\partial\rho}{\partial t}+\nabla\cdot\left[\left(\rho_0+\rho\right){v}\right]-\...
7
votes
1answer
223 views
What are the major differences between GMRES and FOM?
I am reading Professor Saad's "Iterative Methods for Sparse Linear Systems" (2nd edition).
The basic algorithm for FOM is given on page 166 and the basic algorithm for GMRES is given on page 172.
...
8
votes
0answers
138 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, ...
1
vote
1answer
111 views
Questions about iterative projection methods in Saad book
I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results.
In the statements of the propositions, what does it mean ...
1
vote
0answers
196 views
Is reduced stiffness matrix positive definite too?
The stiffness matrix $K$ in a finite element analysis is a symmetric positive definite matrix. When we introduce essential boundary conditions, we remove rows and columns associated with prescribed ...
1
vote
0answers
36 views
Name for vectors in a Krylov space but not the preceding one
It seems to me that a useful concept to define when studying Krylov subspace methods is the idea of a vector that belongs to a Krylov subspace $\mathcal{K}_{n+1}(A,b)$ but not to the preceding one $\...
2
votes
1answer
248 views
Why do we need orthonormal basis of Krylov subspaces for GMRES?
The GMRES method is for solving the linear system $Ax=b$.
Given an initial guess $x_0$ and the corresponding residual $r_0:=b-Ax_0$, we have the Krylov subspace
$$\mathcal{K}_m:=\mathop{span}\{r_0,...
3
votes
3answers
236 views
For which problems Krylov subspace methods are preferred over multigrid methods?
As multigrid methods are known to have grid independent convergence rates with $O(N)$ computational cost, then why would one be interested in using Krylov subspace methods at all, for which ...
1
vote
1answer
88 views
GMRES : incomplete Krylov-subspace
At each iteration $i$ of the GMRES method, is calculated a single new orthonormal vector of the existing Krylov subspace. If the norm of that vector is 0 (or close to 0), then the subspace is "...
0
votes
1answer
86 views
Iterative single variable solutions in large linear systems
I have a system where $A$ is a large $n\times n$ marix with fast MVMs. It may have many nonzero entries (albeit in a structured way so as to allow fast MVMs), and is not necessarily diagonally ...
2
votes
0answers
128 views
Generalized eigenvalue with null space
Define $S\in\mathbb{R}^{n\times n}$ as
$$S:=H+Q^\top V^{-1} Q.$$
$H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for ...
5
votes
2answers
399 views
PetSc vs Sundials for serial numerical computations?
I am currently working on a physics problem that turns into a non-linear boundary value problem. I need an efficient numerical solver that I could run on my laptop with i5 dual core CPU. I am ...
4
votes
2answers
2k views
A numerical GMRES example
I'm having trouble understanding how GMRES works. I've read the part in Saad's book and a few others but still I am confused. Can someone provide me a numerical example to understand it better? Or if ...
5
votes
3answers
362 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 ...
8
votes
2answers
268 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} :=& ...
3
votes
0answers
107 views
Conjugate gradient: the 1-norm of the residual
I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$. ...
2
votes
0answers
184 views
Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?
I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
2
votes
0answers
147 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 & B_v^...
4
votes
1answer
234 views
Appropriate iterative linear solver for an eigenvalue problem
I'm trying to solve a generalized eigenvalue problem
$$Ax = \lambda Bx, \quad A = A^\top > 0,\; B = B^\top > 0$$
with $\lambda \approx \sigma$ using Rayleigh Quotient Iteration (RQI) (RQI is ...
4
votes
1answer
185 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 ...
3
votes
1answer
204 views
Trust-region Newton: implementation issue with Conjugate Gradient calculations
UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ...
13
votes
1answer
799 views
How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?
Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence:
Compute the residual $r_i = b-Ax_i$
...
1
vote
0answers
152 views
Search Direction in Conjugate Gradient
Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
9
votes
1answer
143 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 ...
9
votes
1answer
401 views
Algorithm to calculate the exponential of an Hessenberg matrix
I am interested in computing the solution of a lage system of ODEs using a krylov method as in [1]. Such method involve functions related to the exponential (the so-called $\varphi$-functions). It ...
12
votes
2answers
682 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 ...
8
votes
0answers
215 views
Wanted: sequences of linear systems for recycling Krylov solver analysis
In the solution of sequences of linear systems
$$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$
with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
15
votes
2answers
413 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, ...
7
votes
2answers
1k views
Convergence/stagnation of BiCGStab(l)
I am solving 3D time-harmonic Maxwell FDFD problems (which result in huge sparse linear systems) using BiCGStab(l). I have tried out a bunch of different methods and for my specific use case, it seems ...
7
votes
1answer
484 views
Are there any libraries out there that implement block Krylov subspace methods?
Question
Are there libraries out there that implement block Krylov subspace methods? (I was not able to find any from a simple Google search.)
Background
Right now, I am working with a code that ...
7
votes
2answers
129 views
Convergence of adaptive finite elements with inexact solves
I'm working on some adaptive discontinuous Galerkin codes for time harmonic wave propagation, currently just Helmholtz, but will be branching out once I have a working prototype in this case.
There ...
12
votes
2answers
2k 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 ...
5
votes
2answers
222 views
Are there any specialized methods available for solving structurally symmetric sparse linear systems?
When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is ...
5
votes
3answers
345 views
PRIMA gives an unstable result?
I am working with Modified Nodal Admittance representation of circuits. I am doing Model Order Reduction using PRIMA on MATLAB. I am considering these circuits as Descriptor State-Space systems.
I ...
11
votes
4answers
822 views
Calculating determinant while solving $Ax=b$ using CG
I am solving $Ax=b$ for a huge sparse positive definite matrix $A$ using the conjugate gradient (CG) method. It is possible to compute the determinant of $A$ using the information produced during the ...
6
votes
2answers
263 views
Krylov subspace iterative methods in floating point arithmetic
Is there any work that considers Krylov subspace iterative methods in floating point arithmetic? I'm especially interested in how rounding errors influence the convergence and the accuracy of the ...
12
votes
1answer
978 views
Why is pinning a point to remove a null space bad?
A Poisson equation with all Neumann boundary conditions has a single constant dimensional null space. When solving via a Krylov method, the null space can be removed either by subtracting the mean of ...
15
votes
1answer
557 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 ...
14
votes
1answer
261 views
How do low rank modifications affect Krylov method convergence?
Say I have a linear system $A x = b$, which converges quickly using a suitable Krylov method (such as CG or GMRES) for all $b$. If $B$ is a matrix with low rank $r$, will the same Krylov method on ...
6
votes
1answer
165 views
Identifying the name/provenance of a technique to find the nullspace vectors of a matrix by random sampling and the conjugate residual method
I have got a large sparse matrix $A \in \mathbb R^{n \times n}$ and I want to find non-trivial elements in the kernel/nullspace of this matrix. How can this be done? I would like to learn more about a ...
22
votes
3answers
760 views
Solving $(G^TA^{-1}G)x = b$ without inverting $A$
I have matrices $A$ and $G$. $A$ is sparse and is $n\times n$ with $n$ very large (can be on the order of several million.) $G$ is an $n\times m$ tall matrix with $m$ rather small ($1 \lt m \lt 1000$) ...
0
votes
1answer
917 views
A Comparison between GMRES, QMR and LU for Dense Matrices
As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU.
Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is ...
11
votes
1answer
426 views
How to establish that an iterative method for large linear systems is convergent in practice?
In computational science we often encounter large linear systems which we are required to solve by some (efficient) means, e.g. by either direct or iterative methods. If we focus on the latter, how ...
7
votes
2answers
1k views
Understanding OpenCL performance
I'm using ViennaCL's interface to Eigen as a way to leverage OpenCL. Specifically, I'm using the ::viennacl::linalg::bicgstab_tag with an Eigen sparse matrix. ...
23
votes
3answers
3k views
What is the principle behind the convergence of Krylov subspace methods for solving linear systems of equations?
As I understand it, there are two major categories of iterative methods for solving linear systems of equations:
Stationary Methods (Jacobi, Gauss-Seidel, SOR, Multigrid)
Krylov Subspace methods (...
15
votes
1answer
2k views
Can a Krylov subspace method be used as a smoother for multigrid?
As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
6
votes
3answers
1k views
Krylov Subspace Methods for Dense Systems
I am currently researching on the viability of using KS methods for solving large dense systems. What I wish to prove (or disprove) is that methods like CG, BiCG and QMR are as good (if not better) ...
24
votes
2answers
11k 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 ...
