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

1
vote
2answers
83 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
71 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 ...
1
vote
2answers
134 views

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

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
77 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 ...
0
votes
0answers
19 views

Am I using cyclic reduction to parallelize this algorithm?

I am attempting to implement a modified anisotropic-diffusion filter on the GPU. The methodology I describe here including the equations and code listing are taken from this paper . The author of ...
1
vote
1answer
86 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
62 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
86 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
59 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
56 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
149 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 ...
2
votes
2answers
141 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
96 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
133 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
195 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
56 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
64 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
278 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
155 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
103 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
81 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
178 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
68 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
502 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
326 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
83 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
147 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
115 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
265 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
126 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
69 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
121 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
67 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} = ...
10
votes
1answer
480 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 ...
8
votes
2answers
245 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
144 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
375 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
2answers
182 views

Hartree Fock iteration problem

I am writing a program to compute the ground state energy for any closed shell atom using Hartree Fock Roothaan method, with GTO basis. The code works for the simplest case, the helium, but it fails ...
5
votes
1answer
79 views

Can we compare the speed of convergence of two different iteration methods of same order looking at their error estimates?

I have a two iterative method for approximating the inverse of given square matrix $A$ whose error terms are given as follows Error estimate of method $1$: $\lVert A^{-1} - X_{k}\rVert \leq ...
0
votes
0answers
45 views

Question about Logarithmic convergence

I examine the following recursion $X_{n+1}=\frac{t_n}{t_{n+1}}X_n+\frac{Y_n}{t_{n+1}}$ where $X_n,Y_n$ are positive finite random variables and $t_n$ the time. I have shown that $\lim_{n \to \infty} ...
13
votes
1answer
258 views

Using fixed point iteration to decouple a system of pde's

Suppose I had a boundary value problem: $$\frac{d^2u}{dx^2} + \frac{dv}{dx}=f \text{ in } \Omega$$ $$\frac{du}{dx} +\frac{d^2v}{dx^2} =g \text{ in } \Omega$$ $$u=h \text{ in } \partial\Omega$$ My ...
2
votes
1answer
224 views

Is it possible to ensure global convergence of a fixed point iteration?

Suppose I have a fixed point iteration of the form $$x_{n+1}=f(x_n).$$ Suppose further that after some initial testing, I found that it does not converge to an a priori known fixed point $x^*$. I ...
2
votes
1answer
273 views

Convergence of GMRES

From what I understand the GMRES method is (using Arnoldi Iterations/Modified Gram-Schmidt): The first vector of the Krylov subspace span of A is the normalized vector $\frac{\vec b - A\vec x_0} {|| ...
3
votes
1answer
145 views

Jacobi Iteration diverges?

I'm working through a problem in a textbook as follows: "Consider the $d \times d$ Toeplitz matrix $$ A = \left[ \begin{array}{ccccc} 2 & 1 & 0 & \cdots & 0 \\ -1 &2 ...
2
votes
0answers
59 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. ...
8
votes
2answers
198 views

Looking for an algorithm that allocates climbing hold colors to wall sectors

I posted this question earlier on stackoverflow, where it was closed as off-topic. I hope it survives here. I our climbing gym, the routes need to be re-set from time to time. The following rules ...
5
votes
2answers
109 views

Levenberg optimizer halts quickly when given more variables, or fewer constraints

I'm using the g2o C++ optimization library to refine a GPS trajectory using accelerometer data. The program uses a Levenberg-Marquardt optimizer over data points representing the position and ...
5
votes
4answers
728 views

Fastest polynomial root finder for a given accuracy

I am looking for a very fast polynomial root finder, hopefully with a matlab code. I don't need very accurate results, 2-3 decimal places would be fine. Also the method should be able to optionally ...
10
votes
3answers
2k views

Understanding the “rate of convergence” for iterative methods

According to Wikipedia the rate of convergence is expressed as a specific ratio of vector norms. I'm trying to understand the difference between "linear" and "quadratic" rates, at different points of ...
0
votes
2answers
188 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...