Questions tagged [iterative-method]

A method which produces a sequence of numerical approximations which converges (provided technical conditions are satisfied) to the solution of a problem, generally through repeated applications of some procedure. Examples include Newton's method for root finding, and Jacobi iteration for matrix-vector solves.

Filter by
Sorted by
Tagged with
3
votes
1answer
58 views

Does the k-th approximate solution of a stationary iteration belong to the k-th Krylov subspace?

For an stationary iteration method solving $Ax=b$ as follows: $$ Mx_k = Nx_{k-1}+b, $$ I have known that when $M = I$, i.e., the Richardson iteration, the k-th solution $x_k = x_{k-1}+r_{k-1}$ is in ...
2
votes
1answer
68 views

What is the standard, extrapolation, and modified version of Richardson iteration method?

I have been studying the iterative methods recently. For classical iterative methods solving $Ax=b$, I have seen that the most simplest iteration method is the so-called "Richardson iteration". But I ...
2
votes
1answer
169 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 ...
1
vote
1answer
73 views

Why do not we choose the error solution norm as an iterative method's criterion?

For solving linear system $$ Ax=b, $$ using iterative mehods, we often use the terminate criterion as follows: $$ \frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps. $$where $x_0$ is the ...
0
votes
0answers
49 views

Why does the initial guess for linear system usually choose by zero vector?

For solving linear system $$ Ax=b, $$ using iterative mehods, we often use the terminate criterion as follows: $$ \frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps. $$where $x_0$ is the ...
0
votes
1answer
72 views

How to implement Geometric Multigrid in non-rectangular grids?

It is quite easy to implement multigrid on a rectangular grid but what about an non-rectangular?How to coarse a non-rectangular grid and apply multigrid(assume an easy non-rectangular grid capital ...
3
votes
0answers
44 views

Subspaces for Iterative methods

In the original paper of Conjugate Gradients, the authors mention that if we pick the canonical basis $\{e_1,e_2,\ldots,e_n\}$, to obtain A-orthonormal vectors, we end up with the Gaussian elimination ...
3
votes
1answer
69 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, ...
4
votes
1answer
381 views

Finding interior eigenvalues using Davidson algorithm

Is it possible to find interior eigenvalues closer to some lambda using Davidson method? I was searching online but found that most people use Jacobi-Davidson method for that.
3
votes
1answer
97 views

What is the **contraction factor and convergence factor** of a iteration method?

For any iteration method from A=M-N, e.g., $$ Mx_{k+1}=Nx_{k}+b,\quad k=0,1,... $$ we know that it converges iff $\rho(M^{-1}N)<1$. And when it converges, there exists a concept called asymtotic ...
1
vote
1answer
148 views

Solve linear system with Newton-Raphson method

Is it possible to solve a linear matrix system $A x = b$ using the Newton-Raphson method? If yes, how can this be done? More special, how is the derivative build?
1
vote
0answers
59 views

Can the standard multigrid performance be used for time-dependent PDEs?

Consider a time dependent pde(i.e u(x,t)).I know when only space-coarsening is used the standard multigrid performance can be applied but what if instead we use only time-coarsening?Can we apply the ...
2
votes
2answers
82 views

Can a direct method like Thomas be used in a multigrid method as a smoother?

As far as I know, multigrid uses stationary iterative methods as smoothers (i.e GS), but can we use a direct method also? For example, in case we have a tridiagonal system (for example 1D heat ...
4
votes
1answer
137 views

Low rank update of QR of inverse

I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step: Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$ ...
2
votes
2answers
207 views

Does iterative method work for singular consistent linear system Ax=b?

Recently, I have been studied iterative methods for large sparse linear system Ax=b, where A is nonsingular, so there is a unique solution x. And the stopping criterion is usually chosen with norm(b-...
1
vote
0answers
47 views

BicgStab is not able to solve while Jacobi or GaussSeidel Methods can

I am trying to solve the 2D laplace equation, $\frac{\partial^2 T}{\partial x^2} + \frac{\partial^2 T}{\partial y^2} = 0; \qquad 0 \lt x \lt 1, \quad0 \lt y \lt 1$ Subjected to the boundary ...
1
vote
2answers
322 views

Evaluation of slope at iteration ith - Newton-Raphson method

I'd like to know how Ansys computes the slope (=stiffness matrix) at point x1 in figure. I'm studying the way in which Ansys uses the Newton-Raphson method when there are nonlinearities. In the slide ...
2
votes
0answers
95 views

Small residual but wrong results

When I use BiCGStab to solve a linear matrix system, I use the relative residual to exit the iteration and output the results. For calculating the relative residual I divide the norm of vector $r$ ...
2
votes
0answers
195 views

Understanding MP-PIC implementation in OpenFOAM

The multiphase particle-in-cell (MP-PIC) method is characterized by mapping particle properties from the Lagrangian coordinates to the Eulerian grid. However, the implementation of this method in ...
0
votes
1answer
145 views

The proper way to assess the error of Jacobi iteration (for 2D Poisson equation)?

Motivation: I'm using 2D regular grid (it's actually a quadtree but I can still treat it as a finite difference thing if I weight-average the solution over smaller scale cells for the purpose of ...
3
votes
2answers
307 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 ...
7
votes
0answers
136 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, ...
3
votes
1answer
379 views

What's the terminology for this alternative minimization algorithm?

Say the model is $F(x_1)G(x_2)Z(x_3) = y \in \mathbb{R}^N$, with $F,G,Z$ explicitly known, we are given observation of $y$ as $y_b \in \mathbb{R}^N$ to find the value of $x_1$, $x_2$, $x_3$ for each ...
6
votes
1answer
308 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 ...
0
votes
1answer
222 views

How to set an initial guess for the iterative solver in Comsol?

How to set the initial guess for the iterative solver GMRES or FGMRES for linear problems (Helmholtz equation of RF module) in Comsol?
1
vote
1answer
98 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 ...
8
votes
3answers
1k views

How does the QR algorithm applied to a real matrix returns complex eigenvalues?

I'm a noob into eigenvalues algorithms, but something call my attention. QR algorithm works with real/complex matrices producing real/complex eigenvalues. However, it can not produce complex ...
2
votes
1answer
716 views

Why my parallel code using MPI is much slower than the serial one?

I know that is not the first time someone asks this question but I'm really confused.I'm new to MPI, and I tried to implement the Jacobi solver for a linear system $Ax=b$. I want to compare the time ...
1
vote
0answers
58 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, ...
3
votes
1answer
195 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 ...
0
votes
0answers
36 views

A preconditioner for self-consistent iteration

I tried to derive a preconditioner for self-consistent iteration similar to section IX in arXiv:0804.2583. For simplicity, consider here only one orbital (one or two electrons) systems. Suppose that ...
5
votes
4answers
3k views

Simulated Annealing proof of convergence

I implemented downhill simplex simulated annealing algorithm. Algorithm is very hard to tune, w.r.t. parameters including cooling schedule, starting temperature... My first question is about ...
2
votes
1answer
149 views

In iterative methods, are matrix decompositions considered useful for implementation?

When we study an iterative method from textbooks, for example, see the Gauss-Seidel Method, the given matrix is decomposed with suitable splittings. In the example, $A = L+U$. So we can proceed with ...
2
votes
1answer
107 views

Blowup of error in Conjugate Gradient method with periodic Dirichlet Poisson matrix

My problem is that the L2-Norm of the residual for the periodic Poisson matrix $P$ is initially decreasing but starts to blow up after a certain number of iterations. The blowup happens earlier the ...
2
votes
1answer
208 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
0answers
320 views

Solving a non-convex optimization problem using fmincon

I am trying to solve a non-convex optimization problem using fmincon(). At each iteration, I am iteratively looking for the optimum value and when the termination ...
0
votes
1answer
98 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 ...
0
votes
2answers
109 views

Overrelaxation with w < 0

Are there any circumstances under which using a value $w < 0$ would help us find a solution in over-relaxation faster than we can with the ordinary relaxation method? Over Relaxation Method: $$x'=...
2
votes
0answers
158 views

Richardson's Iteration, Gradient Method and Spectral Radius

Richardson's iteration introduce a scalar $\alpha$ to the update formula: $$ \textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)} $$ And compute $\alpha$ by minimizing the spectral radius:...
1
vote
1answer
149 views

Conjugate gradient - ill-conditioning and numerical tolerance

I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method. Is ...
0
votes
1answer
45 views

Time iteration no longer smooth after using scaled units

I have a time iteration function looked on a 2D surface like this. Since the numbers wee very small i.e. hbar=6.6260700404e-34./(2*pi), my professor told me to use our own "scaled unites" during the ...
1
vote
1answer
52 views

Wrong results for $2$ stage multistep method $y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$

I need to fix a code to utilise the $2$ stage multistep method : $$y_{n+2} - y_n = h\left[(1/3)f_{n+2} + (4/3)f_{n+1} + (1/3)f_n\right]$$ Since this is an implicit method, I used a Newton-Raphson ...
7
votes
2answers
2k views

Markov (Chain) image generators?

Markov Chains can be used to generate, or auto-complete, text. https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators Training text is read, and some information about the text is ...
4
votes
0answers
237 views

Nonlinear least squares and regularization

Consider the nonlinear least-squares minimization of a vector of $n$ residuals $\mathbf{f}$ in $p$ parameters $\mathbf{x}$: $$ \min_{\mathbf{x}} || \mathbf{f}(\mathbf{x}) ||^2 $$ This can be done with ...
1
vote
1answer
528 views

Operation count for GMRES

One can use GMRES as it is, but there is also a version of GMRES called k-step restarted GMRES, which is used for large matrices, where $k$ is some fixed number of steps after which we take a new $x_0$...
1
vote
2answers
187 views

Finding null vectors of a parameter-dependent matrix

I have dense complex matrices $M(z)$ in which each element $M_{ij} = M_{ij}(z)$ depends on a complex parameter $z$. I need to find $z$ such that the matrix $M$ gets singular, i.e. I am looking for ...
5
votes
0answers
78 views

Improving convergence of Jacobi iteration to Schur form

I'm using SIMD processor arrays to compute the eigen-decomposition for large numbers of small (up to $32\times 32$) matrices. For assorted technical reasons, Jacobi iteration maps well to the SIMD ...
1
vote
1answer
272 views

What is the default smoother for the “PCMG” preconditioner in PETSc?

For a large parallel sparse matrix (mpiaij type matrix) in my code, I was experimenting with various preconditioners to see which one would do best with GMRES/BiCGSTAB. I tried the PCMG ...
1
vote
0answers
34 views

Logging vs outputs in iterative optimisation

I'm coding an iterative algorithm of constrained continuous optimisation. An augmented Lagrangian algorithm (outer) calls a bound-constrained L-BFGS-B algorithm (inner), which calls a line search ...
10
votes
2answers
1k views

Which iterative linear solvers converge for positive semidefinite matrices?

I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$ (...