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 ...
5
votes
1answer
40 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
57 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 ...
0
votes
1answer
63 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} {|| ...
2
votes
1answer
91 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
52 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. ...
7
votes
2answers
151 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
54 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 ...
4
votes
3answers
156 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 ...
9
votes
3answers
256 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
102 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 ...
4
votes
2answers
107 views
Krylov subspace iterative methods in floating point arithmetic
Is there any work that considers Krylov subspace iterative methods in floating point arithmetic? I'm especially interested in how rounding errors influence the convergence and the accuracy of the ...
5
votes
2answers
261 views
How to remove Rigid Body Motions in Linear Elasticity?
I want to solve $K u = b$ where $K$ is my stiffness matrix. However some constraints may be missing an therefore some rigid body motion may be still present in the system (due to eigenvalue zero). ...
3
votes
2answers
118 views
Does right-hand side influence convergence rate of a Krlylov supspace method?
Consider general system $Ax=b$. Does convergence of the Krylov subspace methods depend on actual vector $b$ assuming initial guess is zero? I mean such factors as locality of the source (with the ...
8
votes
1answer
130 views
What is the current state of polynomial preconditioners?
I wonder what has happened to polynomial preconditioners. I am interested in them, because they appear to be comparatively elegant from a mathematical perspective, but as far as I have read in surveys ...
5
votes
3answers
296 views
Eigenvectors with the Power Iteration
To compute the eigenvector corresponding to dominant eigenvalue of a symmetric matrix $A\in\mathbb{R}^{n\times n}$, one used Power Iteration, i.e., given some random initialization, ...
4
votes
4answers
406 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 ...
1
vote
3answers
153 views
Convergence of the gradient descent and linear vs non-linear fixed point iteration
Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can ...
6
votes
2answers
648 views
How to choose a method for solving linear equations
To my knowledge, there are 4 ways to solving a system of linear equations (correct me if there are more):
If the system matrix is a full-rank square matrix, you can use Cramer’s Rule;
Compute the ...
7
votes
5answers
275 views
Iterative solution to a nonlinear equation
I appologize in advance if this question is silly.
I need to compute the root of
\begin{equation}
u -f(u) =0
\end{equation}
Where $u$ is a real vector and $f(u)$ is a real-vector valued function.
...
5
votes
2answers
146 views
Basin of attraction for Newton's method
Newton's method for solving nonlinear equations is known to converge quadratically when the starting guess is "sufficiently close" to the solution.
What is "sufficiently close"?
Is there literature ...
7
votes
1answer
154 views
Is the sparsity pattern of a linear system important for iterative (KSP) solvers?
Pretty much the question. Given a general sparse, non-symmetric (both numerically and structurally) matrix, how important is the sparsity pattern (i.e. row/column permutation of matrix/vector) for ...
7
votes
1answer
130 views
Solving a system with a small rank diagonal update
Suppose I have the original large, sparse linear system: $A\textbf{x}_0=\textbf{b}_0$. Now, I do not have $A^{-1}$ as A is too large to factor or any sort of decomposition of $A$, but assume that I ...
6
votes
2answers
222 views
What is a robust, iterative solver for large 3-d linear-elastic problems?
I'm diving into the fascinating world of finite element analysis and would like to solve a large thermo-mechanical problem (only thermal $\rightarrow$ mechanical, no feedback).
For the mechanical ...
10
votes
1answer
270 views
Projecting out the null-space of $A$ from $b$ in $Ax=b$
Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
3
votes
2answers
159 views
How to establish that an iterative method can be applied to large matrices whose size may reach 10^3?
I have an iterative method for computing the Moore-Penrose generalized inverse of matrices, that is
$$X_{k+1} = ((I-\beta X_{k}A)^t) + X_{k}$$
with initial approximation:
$$X_{0} = \beta AA^t$$
...
1
vote
1answer
113 views
Gradient descent to stationary, or accumulation point
I recently came across the notion of an accumulation point as a result of a certain gradient descent variation. The following definition was found:
An accumulation point $P$ is such that there are an ...
0
votes
3answers
183 views
Unique coordinates (solutions) in a single Gauss-Seidel iteration
I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices ...
0
votes
1answer
237 views
A Comparison between GMRES, QMR and LU for Dense Matrices
As I see it, there are 3 ways to solve unstructured dense system of equations: GMRES, QMR and LU.
Has anyone done a comparison for these three? As far as I know, LU is the preferred choice and it is ...
6
votes
2answers
598 views
Safe application of iterative methods on diagonally dominant matrices
Suppose the following linear system is given
$$Lx=c,\tag1$$
where $L$ is the weighted Laplacian known to be positive $semi-$definite with a one dimensional null space spanned by ...
3
votes
3answers
226 views
On Vanilla Preconditioners for solving dense $Ax=b$ iteratively
I am looking for preconditioners which don't assume anything about the matrix or its origins.
I basically want to be able to type in the following in MATLAB and have quick solving time:
...
4
votes
4answers
179 views
Determining the algorithmic complexity
A few of the iterative matrix algorithms (CG,GMRES etc.) I have authored are acting rather funny. They converge to the right answers but take abnormally long time to run. I am in the process of ...
5
votes
1answer
264 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)$
...
6
votes
1answer
366 views
Jacobi iteration to reduce the quadratic function
Given certain function $f(X)$ which is quadratic in $X\in\mathbb{R}^{n\times d}$,
$$\frac{1}{2}tr(X^TAX) - tr(Y^TBX)$$
for positive definite weighted Laplacian matrices $A, B\in\mathbb{R}^{n\times ...
5
votes
1answer
96 views
Question about the smoothing operators in multigrid methods for nonlinear PDEs
Suppose we are dealing with a nonlinear problem, say
$$
A u := L u + G(u) = f
$$
the nonlinearity of the operator $A$ is the polynomial type, ie, $L$ is a linear operator, and $G(u) = u^k$, or ...
8
votes
1answer
196 views
How to establish that an iterative method for large linear systems is convergent in practice?
In computational science we often encounter large linear systems which we are required to solve by some (efficient) means, e.g. by either direct or iterative methods. If we focus on the latter, how ...
6
votes
3answers
275 views
Why does iteratively solving the Hartree-Fock equations result in convergence?
In the Hartree-Fock self-consistent field method of solving the time-independent electronic Schroedinger equation, we seek to minimize the ground state energy, $E_{0}$, of a system of electrons in an ...
15
votes
3answers
354 views
What guidelines should I use when searching for good preconditioning methods for a specific problem?
For the solution of large linear systems $Ax=b$ using iterative methods, it is often of interest to introduce preconditioning, e.g. solve instead $M^{-1}(Ax=b)$, where $M$ is here used for ...
4
votes
1answer
775 views
Are there any heuristics for optimizing the successive over-relaxation (SOR) method?
As I understand it, successive over relaxation works by choosing a parameter $0\leq\omega\leq2$ and using a linear combination of a (quasi) Gauss-Seidel iteration and the value at the previous ...
8
votes
1answer
251 views
Can a Krylov subspace method be used as a smoother for multigrid?
As far as I am aware, multigrid solvers use iterative smoothers such as Jacobi, Gauss-Seidel, and SOR to dampen the error at various frequencies. Could a Krylov subspace method (like conjugate ...
6
votes
3answers
270 views
Iterative methods for indefinite systems without block structure
Indefinite systems of matrices appear for example in the discretization of saddle point problems by mixed finite elements. The system matrix can then be put in the form
$$\begin{pmatrix} A & B^t ...
4
votes
3answers
450 views
Krylov Subspace Methods for Dense Systems
I am currently researching on the viability of using KS methods for solving large dense systems. What I wish to prove (or disprove) is that methods like CG, BiCG and QMR are as good (if not better) ...
5
votes
1answer
329 views
What is a good stop criterion when using an iterative method to find eigenvalues?
I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors.
What are good stop ...
9
votes
2answers
1k views
Why is my iterative linear solver not converging?
What can go wrong when using preconditoned Krylov methods from KSP (PETSc's linear solver package) to solve a sparse linear system such as those obtained by discretizing and linearizing partial ...
