Questions tagged [krylov-method]
Referring to Krylov Subspaces and the methods of solutions to linear systems of equations which exploit these spaces.
61
questions
2
votes
0answers
58 views
Solving a huge least squares system of equations when I can only evaluate Ax
I have a situation where I can generate a system of $M$ linear equations for $N$ variables ($N \ne M$). Implicitly this is of the form $Ax=b$ with $A \in \mathbb{R}^{M \times N}$, although I never ...
1
vote
2answers
83 views
How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?
For the Krylov subspace method to solve the large sparse linear system, we first need to generate a subspace Km = span{v,Av,...A^{m-1}v}, which indeed a process ...
3
votes
0answers
53 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 ...
1
vote
0answers
49 views
Numerical methods. MDF (ILU) implementation
I am trying to implement Minimum Discarded Fill (MDF) Ordering algorithm for incomplete matrix factorization. The algorithm description is here on page 60 Preconditioning Techniques for a Newton–...
2
votes
1answer
206 views
How to implement flexible gmres in matlab?
About the flexible GMRES (fgmres), we know that it is a variant of right preconditioned gmres. And the robust command gmres in matlab as follows:
...
1
vote
0answers
47 views
How to compute the computational cost and storage of the Full Orthogonalization Method?
About the analysis of Full Orthogonalization Method (FOM) in Prof. Saad's book, wrote as follows:
Algorithm 6.4 (FOM):
\begin{array}{l}
r_0=b-Ax_0,\beta=\|r_0\|_2,v_1 = r_0/\beta\\
Define \quad H_m ...
2
votes
0answers
60 views
How to reproduce the numerical examples in Prof. Saad's Book about Krylov subspace methods?
After reading Prof. Saad' Book, "Iterative methods for Sparse Linear Systems, 2nd version", I want to do the numerical examples about the Krylov subspace methods not only to reproduce the results in ...
5
votes
1answer
467 views
Why MATLAB chooses the Householder in its built-in function gmres.m?
Recently, I have studied how to construct an orthonormal basis for Krylov subspace to solve $Ax=b$, where $A\in \mathbb{R}^{n\times n}$ is nonsingular. As we know, there are usually 4 ways to ...
2
votes
2answers
72 views
How to understand the choice of Krylov subspace orthonormal basis?
This semester, I study the Krylov subspace iterative methods (about Ax=b) using the book H. A. Van der Vorst. Iterative Krylov Methods for Large Linear Systems,
volume 13. Cambridge University Press, ...
2
votes
1answer
138 views
What's wrong with the **PCG and MINRES** in matlab?
Last week, I have learned the details of the robust iterative methods of PCG, MINRES, GMRES, which will converges to the exact solution $x^*$ of nonsingular system within $N$ steps for $A\in \mathbb{R}...
2
votes
1answer
114 views
Why Krylov subspace iterative methods are faster than classical iteration?
This semester, I have been studying the most popular iterative methods, i.e., Krylov subspace iteration methods.
For a large sparse system linear
$$
Ax=b,
$$
where $A$ is nonsingular, I know that ...
5
votes
0answers
39 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
49 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 ...
2
votes
1answer
149 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]-\...
13
votes
1answer
338 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
1answer
211 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
115 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
243 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
37 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
293 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
265 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
2answers
118 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
89 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
138 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
438 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 ...
5
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 ...
6
votes
3answers
523 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
292 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
109 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
205 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
153 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
250 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
195 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
212 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
893 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
147 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
420 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 ...
13
votes
2answers
724 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
223 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
445 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
513 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
132 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
351 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
873 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
274 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 ...
13
votes
1answer
1k 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 ...
