# Tagged Questions

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

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 ...
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 ...
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} {|| ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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). ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$$ ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 12, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9037252068519592, "perplexity_flag": "middle"}