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-...

learn more… | top users | synonyms

0
votes
1answer
54 views

Exact distribution of random walk after 10 or 100 steps

(Variant of Stats Exercise to Protect the Innocent). Starting for $x = 0$ I can do one of two operations $\pm 1$ or $\pm 4$. Let $T$ be one iteration of this step. What is the mean and standard ...
1
vote
0answers
23 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 ...
3
votes
1answer
37 views

Lanczos algorithms for Hermitian system with toeplitz kernel

Basically I am trying to compute the SVD of a large hermian matrix H using Lanczos iteration, while H consists if a toeplitz kernel K, which should be able to help speed up the matrix-vector ...
2
votes
0answers
11 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 ...
4
votes
1answer
69 views

Convergence conditions of a stationary iteration method for linear systems

Recently, I obtain a linear system, $Ax = b$, where $A$ is a nonsingular, strictly diagonally dominant $M$-matrix. Then I also got a matrix splitting $A = S - T$, where $S$ is also a nonsingular, ...
0
votes
1answer
66 views

Linear stationary iteration method

Suppose you are attempting to solve $Ax = b$ using linear stationary iteration method defined by $$x_k = G x_{k-1} + f$$ that is consistent with $Ax = b$, i.e., for which $f = (I - G)A^{-1}b$. Suppose ...
8
votes
1answer
145 views

Integer vs float multiplication performance, modern CPUs

Are there benchmarks for how many multiplications of various integer types compared to floating point types can be achieved per second on modern CPUs? I'm trying to get some hint if it would be ...
4
votes
0answers
109 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 ...
1
vote
1answer
135 views

How to solve the problem without using symbolic computation

I have the following simple nonlinear equations with two unknowns only: $$\left\{ \begin{array}{c} \int_1^2{\dfrac{ e^{{a_1} x+{a_2} x^3}}{1+x^2}} \, dx=1 \\[13pt] \int_1^2{ x^2 e^{{a_1} x+{a_2} x^...
0
votes
0answers
51 views

Gauss-Seidel iteration weighted by change

In general, I can use Gauss-Seidel iteration for finite difference solution of partial differential equations. In my case I am only solving an analog of steady-state heat transfer, so there is no ...
0
votes
0answers
23 views

what's the optimal parameters to reach the maximum speed of GAMG algorithm

everyone! As the GAMG algorithm has many parameters to set, how can I reach the maximum speed? Is there any optimal parameters range for any CFD models? or I have to try every parameters to reach the ...
3
votes
1answer
125 views

Is this finite difference approach correct?

I am solving incompressible 2D Navier-Stokes equations with zero y-component velocity. The geometry is a simple 2D pipe of a length $L$ and diameter $W$ and there is only two boundary conditions: ...
2
votes
0answers
26 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? ...
0
votes
0answers
32 views

Learning Lanczos eigenvalue iteration - what is wrong?

I try to familiarize myself with iterative eigenvalue solvers such as Lanczos. So I tried rewrite it to python directly according to wiki. But it doesn't seem to work. The problem: it approximates ...
5
votes
1answer
79 views

Eigenvectors of slightly perturbed matrix

Assume I know eigen-pairs $(\epsilon_i,\vec\phi_i)$ for matrix operator $\hat H$ that $ \hat H \vec \phi_i = \epsilon_i \vec \phi_i $ Now I have slightly perturbed $\hat H' = \hat H + \hat R$ were ...
4
votes
1answer
112 views

Power Iteration over Rayleigh Quotient Iteration?

It is a commonly known fact that the Rayleigh Quotient converges cubically (1), while the Power Iteration may converge slowly if the difference between the dominant and second-dominant eigenvalue is ...
1
vote
0answers
52 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 ...
11
votes
1answer
281 views

Smallest eigenvalue without inverse

Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly. Is there an iterative algorithm for finding the ...
1
vote
1answer
112 views

Iterative Closest Point Algorithm

I am currently working on an iterative closest point algorithm (in C++, see here). I understand the basic premise of an ICP algorithm. You have two point clouds (a target and a reference) and you ...
7
votes
0answers
88 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 ...
0
votes
1answer
82 views

Variational Monte Carlo: Variational energy is lower than ground state energy

I'm writing a VMC simulation for hydrogen and helium atoms, but in both my codes my variational energy for certain wavefunctions is not only statistically different from my expectation value, but it ...
2
votes
0answers
59 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....
9
votes
1answer
198 views

Iterative “solver” for $x^t \Sigma^{-1} x$

I can't imagine I'm the first to think about the following problem, so I'll be satisfied with a reference (but a complete, detailed answer is always appreciated): Say you have a symmetric positive ...
4
votes
0answers
64 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. ...
1
vote
1answer
74 views

Convergence problem in iterative method

I am trying to solve two non-linear equations self-consistently in a Gummel loop. Sometimes (every once in a while), I get to a situation when the loop repeats itself with wrong solutions and a ...
2
votes
1answer
61 views

Minimizing Cost Functions using Iterative Least Squares

I am currently trying to use iterative least squares to solve a system, $y = Hx + v$ where $y$ is a vector of observations, $H$ is the design matrix, and $v$ is the observation error. From my ...
9
votes
1answer
131 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
1answer
68 views

Incomplete Cholesky

Is there an efficient way to perform an incomplete Cholesky factorization on a symmetric positive definite sparse matrix (CSR format), in order to use it as a preconditioner for a CG solver? Is there ...
5
votes
1answer
376 views

Can Gauss-Seidel/SOR (preconditioned?) be applied to a non-diagonally dominant matrix?

After applying finite difference method to a Laplace/Poisson problem always arises a diagonal dominant system of equations that can be solved with Gauss-Seidel or SOR methods. If the original PDE does ...
2
votes
1answer
135 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 ...
2
votes
2answers
143 views

FLOPs of iterative vs direct solvers

In general, do iterative solvers require more floating point operations than the direct solver counterparts? I have some scientific code (written in both PETSc and FEniCS) for solving a mixed FE ...
0
votes
1answer
117 views

Strict Feasibility in Interior Point Methods

As we know, in the interior point methods, all the iterates have to be strictly feasible. I implemented an affine scaling interior point for nonlinear objective functions. For small examples (2D), it ...
0
votes
2answers
289 views

How to obtain a convergent solution iteratively for a linear system of equations? [closed]

I am working on a problem that requires an iterative procedure to solve a linear system of equations, the system of equations in matrix form is: $$\underbrace{\begin{bmatrix} r_{11} & r_{12} &...
4
votes
1answer
92 views

How to evaluate a series of derivatives?

Consider the function $$f(\mathbf{x}) = \sum_{n=0}^{N} a_n \left( (\mathbf{b}-\mathbf{x})\cdot \nabla \right)^n \frac{1}{r}$$ where $r = |\mathbf{x}| = \sqrt{(x-x_0)^2 + (y-y_0)^2}$ and $a_n$ and $\...
1
vote
1answer
149 views

Direct or iterative solver for ill-conditioned problems

I have to solve an ill-conditioned sparse matrix. Once I read that iterative solver are the better tool for such problems. Is that true? If yes, why?
1
vote
0answers
108 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 ...
4
votes
1answer
128 views

Methods for Constrained Optimization Problems with Box Constraints

Consider this problem: \begin{equation} \begin{array}{ll} \text{minimize } & f(x) \\ \text{subject to } & a \leq x \leq b \end{array} \end{equation} where $a,b,x \in \mathbb{...
0
votes
1answer
71 views

Iterative algorithms for sparsity using a function for operator A in Ax=b

I am going to solve an linear iterative inverse problem. I have two functions in matlab which one of them play the forward and ...
1
vote
0answers
138 views

Speeding up the classical Jacobi method using Scheduled Relaxation method? [closed]

There has been quite a flutter recently in the iterative world about an algorithm that speeds up the classical Jacobi method by as much as 200 times using a scheduled relaxation method where a ...
3
votes
1answer
214 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 ...
3
votes
2answers
265 views

How many generations does it typically take for a differential evolution method to reach a global optimum?

For differential evolution methods in optimization, how many generations does it typically take to reach a global optimum? How do we know if the values are never going to converge?
1
vote
3answers
152 views

Test set for linear solvers

Lets assume I have a iterative linear system solver, e. g. this one. Whats the typical approach on verifying and testing this kind of solvers? Is there a standard test set of linear systems one ...
3
votes
2answers
580 views

What are some reasons that Conjugate Gradient iteration does not converge?

I would greatly appreciate it if you could share some reasons the Conjugate Gradient iteration for Ax = b does not converge? My matrix A is symmetric positive definite. Thank you so much! Edit with ...
2
votes
1answer
831 views

How to test convergence of an algorithm for constrained optimization

I am applying an iterative method (projected newton) to an optimization problem. Theoretically, the method should converge linearly. I would greatly appreciate it if you could share how should I test ...
4
votes
1answer
58 views

Iteratively refine bounds on exp for Metropolis criterion

In Monte Carlo simulations, using the Metropolis criterion, one often has to compare a random number $a$, $0 \leq a < 1$, to the Boltzmann distribution $exp(-\beta\Delta E)$, where $\Delta E$ is ...
1
vote
2answers
74 views

Performance metrics to compare initial-boundary value problem solutions

I am comparing the performance several finite difference methods of solving an initial-boundary value problem. There are several dimensions to this comparison: Number of cells Number of timesteps ...
2
votes
3answers
432 views

Eigenvalues of a sparse banded nonsymmetric matrix from an elliptic operator

I have a sparse matrix coming from the discretization of a 3D elliptic PDE. The matrix is banded with seven non-zeros diagonals. The sparsity pattern of the matrix looks like this (the actual matrix ...
4
votes
1answer
229 views

Linear equation system: Direct solver works, iterative solver does not

I have to solve for x in b = A*x, where a is sparse. This works fine with Matlab's mldivide: x = A \ b. Since I will have to use an iterative algorithm for very large A, I'm currently testing Matlab's ...
1
vote
1answer
123 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 ...
2
votes
1answer
109 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. Thanks