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

learn more… | top users | synonyms

0
votes
0answers
16 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 ...
10
votes
1answer
229 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
79 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
43 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
0answers
45 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
50 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 ...
9
votes
1answer
185 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
57 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
69 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
55 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
123 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
61 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
346 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
124 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
137 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
113 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
235 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
91 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
136 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
95 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
117 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 ...
0
votes
1answer
67 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
118 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
198 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
188 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
130 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 ...
2
votes
2answers
349 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
600 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
71 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
373 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
210 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
118 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
101 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
1
vote
2answers
325 views

What sparse linear programming solver it is better to use?

I have the following LP problem: $$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; s.t. \;\;C x \geq 0, \;\; x_{i}^{0} - \varepsilon ...
2
votes
0answers
80 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 ...
7
votes
3answers
946 views

Sort of problems where SOR is faster than Gauss-Seidel?

Is there any simple rule of thumb to say if it is worth to do SOR instead of Gauss-Seidel? ( and possible way how to estimate realxation parameter $\omega$) I mean just by looking on the matrix, or ...
2
votes
2answers
597 views

What is the difference between “Newton-type” and “Newton-like” iteration?

Is there any clear classification between different iterative methods? What is the difference between Newton-type and ...
1
vote
0answers
113 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
1answer
244 views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
4
votes
0answers
145 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
396 views

Inverse iteration to find the null singular vector of a rank-deficient matrix

I have an $n \times n$ unsymmetric matrix $A$ that results from the discretization of an ill-posed Poisson problem, and thus is rank-deficient with null space of dimension one. I want to compute just ...
4
votes
1answer
134 views

Factorization for reweighted least squares

I am solving a problem using an iteratively-reweighted least squares method: http://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares Essentially this requires solving a number of ...
6
votes
1answer
75 views

Numerical iterative method, estimating error

Given iterative method: $x_{n+1}=0.7\sin x_n +5 = \phi(x_n)$ for finding solution for $x=0.7\sin x +5$, I want to estimate $|e_6|=|x_6-r|$ as good as possible, with $x_0=5$, where $r$ is exact ...
5
votes
3answers
122 views

Newton's method for a given polynomial

Let $f(x)=\frac{1}{5}x^5+\frac{1}{3}x^3+x-1$ Show that $f$ has only one zero $r$ in interval $(0,1)$ To find approximation of $r$ we apply Newton's method ...
0
votes
0answers
71 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} = ...
11
votes
1answer
669 views

Intuitive motivation for BFGS update

I am teaching a numerical analysis survey class and am seeking motivation for the BFGS method for students with limited background/intuition in optimization! While I don't have time to prove ...
9
votes
2answers
256 views

What is the underlying structure of scientific code performance?

Consider two computers with different hardware and software configurations. When running the exact same serial Navier-Stokes code on each platform it takes x and y time to execute one iteration for ...
4
votes
0answers
175 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 ...
7
votes
2answers
606 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 ...