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.
45
questions with no upvoted or accepted answers
7
votes
0answers
463 views
DIIS method to accelerate SCF convergence for stretched geometries
I am implementing from scratch an Hartree-Fock calculation in the STO-3G basis set to perform Born-Oppenheimer molecular dynamics. I have a Restricted Hartree-Fock procedure that can reproduce very ...
5
votes
0answers
182 views
Conjugate residual/gradient convergence checking in practice
Let's say we want to solve $Ax=b$ ($A$ symmetric positive /semi/definite) with the conjugate residual/gradient method. $A$ comes from FEM where the mesh is being refined. The exact solution is $x_*$ ...
5
votes
1answer
235 views
Robust smoothers for geometric multigrid
I'm searching for robust smoothers for geometric multigrids.
By robust I mean:
Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin),
Parallel (suitable for ...
4
votes
0answers
30 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, ...
4
votes
0answers
73 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 ...
4
votes
0answers
233 views
Solving a PDE implicitly by iteration in python
Connected to this question here on Computational Science, I've posted a follow-up question on how to solve a PDE using an implicit scheme like Crank-Nicholson in general in this question on SO.
But I ...
4
votes
0answers
351 views
Convergence rate of Picard iterations
Given a first order ODE $y'(x)=f(x,y)$ with the initial condition $y(x_0)=x_0$ such that it satisfies Picard thoerem of existence and uniquness, one can compute the solution by Picard iterations :
$$ ...
4
votes
0answers
148 views
Preconditioning technique for large sparse non-hermitian matrix
I am attempting to solve a computational acoustics problem that involves solving an underlying sparse matrix. The size of the problem varies with grid size (3D) and fill-in's obviously make direct ...
4
votes
0answers
125 views
What causes periodic humps in residual plots?
When using many iterative methods, whether for solving linear systems, looking for steady-state convergence in CFD, etc., the semilog plot of the residual often shows "humps" as the residual decays. ...
4
votes
0answers
324 views
Understanding the meaning of Computational Order of Convergence
I am a postgraduate student with interest in numerical methods for solving nonlinear systems of equations. I have read some papers that discussed about 'computational order of convergence' for some ...
3
votes
0answers
40 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
0answers
107 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 ...
3
votes
0answers
114 views
Unstable convergence of a Poisson equation
What could be the reason that the solution of a Poisson equation is smooth when obtained by an iterative solver, only if the maximum residual is set to a high value (e.g. 0.1)? When the maximum ...
3
votes
0answers
70 views
PETSc SNES for user defined state
How to use PETSc SNES (scalable nonlinear equation solver), when the solution is not a vector but a user defined state?
I am implementing a non-linear mechanics problem (geometrically exact shell 5-...
3
votes
0answers
202 views
How to avoid the Broyden's jacobian approximation becoming poorer with the number of iterations?
I have to solve many times a nonlinear system of the form
$$f(x) = b^{(n)}$$
inside a loop.
The function $f$ is expensive to compute and I do not have its jacobian, so I have tried the good Broyden's ...
3
votes
0answers
427 views
full rank update to cholesky decomposition for multivariate normal distribution
This question is a specialization of full rank update to cholesky decomposition, to which I hope to get a more positive answer.
When calculating the minus log of the multivariate normal distribution, ...
2
votes
0answers
83 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
47 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 ...
2
votes
0answers
80 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:...
2
votes
0answers
68 views
Simultaneous update to barycenters
Suppose a tiling is given in 2D (an embedding of a planar triangulated graph), with all faces convex.
Now suppose one moves each point, one by one, to the barycenter of its neighbors. I think that ...
2
votes
0answers
58 views
How can I numerically solve a saddle point problem with repeated constraints?
I am interested in numerically solving the following constrained minimization problem; Find the value of $x\in \mathbb{R}^n$ that minimizes $f$ where
$f\colon \mathbb{R}^n\to \mathbb{R}$ is defined ...
2
votes
0answers
132 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 ...
2
votes
0answers
76 views
Numerical error in implementation of iterative algorithm
I am trying to implement (in Python for now) low thrust orbit propagation for spacecraft using universal variables. For a given central body with the gravitational parameter $\mu$ and an orbit with ...
2
votes
0answers
62 views
Dynamic Successive Over/under Relaxation (SOR) with several variables
I am solving a partial differential algebraic equation (PDAE) system which has the following dependent variables:
$f=f(X,T)$ and $g=g(T)$, along with a few others
My current method for coupling is ...
2
votes
0answers
52 views
SPECT reconstrction using MLEM
In Single-Photon Emission Computerized Tomography (SPECT) parallel beam reconstruction using Maximum-Likelihood Expectation–Maximization(MLEM), is it sufficient to scan the object around 180 degree? ...
2
votes
0answers
194 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
103 views
Modal analysis of structure with aerodynamic damping
I'm using modal decomposition to predict the steady state response of a beam structure to harmonic loading. The structure itself is very lightly damped, but we know from experiments that the ...
2
votes
0answers
71 views
What are Implications of Commutative Diagrams?
This question may be too broad. But I really want to know some concrete explanations. I often find various commutations appear here and there, which concerns the application order of two operators. ...
1
vote
0answers
56 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 ...
1
vote
0answers
34 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
0answers
49 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 ...
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 ...
1
vote
0answers
58 views
Fixed point iteration reduction factor
In a book for solving a nonlinear differential equation with $N+1$ points, $u_{xx} = e^{u}, u(-1)=u(1) = 0$, in $[-1,1]$ with homogeneous Dirichlet boundary conditions, the fixed point iteration is ...
1
vote
0answers
59 views
fourth order Poisson iterative solver --in Matlab
I want to calculate the stream function $\psi$ starting from a velocity field $(u,v)$ (such that $u=-\frac{\partial\psi}{\partial y}$ and $v=\frac{\partial\psi}{\partial x}$). I thus calculate the ...
1
vote
0answers
56 views
bound error for iterative method for solving linear system
$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that
$$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
1
vote
0answers
32 views
Difference between Chebyshev first and second degree iterative methods
Consider linear equation $Au = f$.
We want to solve it with iterative method (assuming $A$ is good).
First order iterative method is:
$$
u^{k+1} = u^k - \alpha_{k+1}(Au^k - f),
$$
The second degree ...
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 ...
1
vote
0answers
85 views
Increase convergence of non-linear equations resulting from ODEs
I am trying to solve a set of couple ODEs:
$V_l(r) - r W_l(r) - f1(r) W_l' = 0\tag 1$
$r^2 h''_l(r) + f2 r h_l'(r) + f3 h_l(r) - f4 U_l(r) = 0 \tag 2$
$\kappa (U_l + h_l) + V_{l+1} + W_{l+1} = 0\...
0
votes
0answers
1 view
Any suggestions to research direction about Krylov subspace iterative methods?
I am a new graduate majoring in matrix computations, especially, about Krylov subspace iterative methods for large sparse linear system, namely,
$$
Ax=b.
$$ I have been reading these classical ...
0
votes
0answers
34 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
78 views
How suitable is multigrid method for time-dependent PDEs?
For elliptic PDEs (Poisson-type), the multigrid method is very sufficient, but how about time-dependent problems (i.e parabolic or hyperbolic PDEs)?
Is it efficient to solve such problems using a ...
0
votes
0answers
32 views
Divergence issues when using intrinsic cohesive elements approach
When I model the strain localisation of a microscopic sample (or say RVE ) with cohesive elements approach, the convergence performance looks very terrible. I have to use extremely time increments (...
0
votes
0answers
27 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 ...
0
votes
0answers
109 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 ...
-1
votes
1answer
241 views
Gauss-Seidel method convergence
I am currently programming a code to find the equilibrium function that satisfies the poisson equation in 2D. In order to do this I use finite difference methods and the discrete equation I want to ...
