Questions tagged [iterative-method]
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-vector solves.
295
questions
1
vote
2
answers
95
views
Implementing matrix term version of Gauss-seidel
I am trying to implement the below description from Ch. 11 of Heath's "Scientific Computing An Introductory Survey" of the Gauss-Seidel iterative method for solving a system of linear ...
- 233
3
votes
0
answers
112
views
Stochastic power iteration for generalized eigenvalue problems?
Suppose $\mathbf{x}$ is a random variable in $n$ dimensions, and $u$ is a vector. How can I estimate the following quantity in an online fashion?
$$f(x)=\max_{\|u\|=1} \frac{ E\left[\langle u\cdot x\...
- 2,273
0
votes
1
answer
65
views
How can I find the current for a nonlinear electrical circuit using the Shockley equation, in Octave?
For this electrical circuit:
The voltage $ V_D $ can be found by solving a nonlinear equation:
$$ \frac{V_{DD}}{R} - \frac{V_D}{R} - I_se^{V_D/V_T} = 0 $$
In this example, let $R=1000$, $V_T = 0.025$,...
- 103
2
votes
2
answers
460
views
Iteration counts of AMG solver changes in parallel
I am solving the linear elasticity equation within a FEM library with a complex 3D geometry. The resulting linear system is solved with CG, preconditioned by AMG (Algebraic Multigrid). The computed ...
- 281
0
votes
0
answers
111
views
Algorithm to solve system of nonlinear equations
I would like some tips in figuring out a good algorithm to find the solution of the following system. Let $\theta$ be a constant in $(0,1)$, let $i,l=1,...,N$, let $a_{l}$ and $b_{i,l}$ be some ...
- 1
0
votes
0
answers
38
views
Equilibrium position finding with DSM
I've coded a framework that can be used to simulate the dynamic behavior of a system discretized by particles (nodes) that are connected by spring-damper elements. However, I want to compare it to a ...
0
votes
0
answers
49
views
Professional orbital simulation software methods, accuracy, runtime
I'm working on an orbital body simulation as a personal project. I understand that it's not going to be as good as professional software, but I'm wondering what contemporary,
general purpose, ...
- 1
4
votes
1
answer
140
views
Is there a way to generate a matrix-free decomposition for a matrix-free operator?
Hypothetical question for some code that I'm writing. Suppose I have an matrix-free linear operator $A$, i.e. the only thing I know about it is the forward action $v \mapsto Av$. For simplicity, let's ...
- 141
0
votes
0
answers
58
views
Compatibility condition for Poisson equation in cylindrical symmetry
I'm trying to implement multigrid approach for a Poisson equation $\frac{1}{r}\frac{\partial}{\partial r}\left( r \frac{\partial H}{\partial r} \right) = f$ with all Neumann boundary conditions. ...
2
votes
1
answer
174
views
Solution of linear system doesn't work, in parallel
I'm solving $Ax = b$ with PETSc, $A$ sparse and asymmetric.
I'm using BCGS or FGMRES or TFQMR as a solver, and ILU as a preconditioner.
When I use 1 core, everything works as expected. But with 8 ...
- 243
2
votes
0
answers
132
views
Does exact diagonalization of a matrix allow for efficient computation of a Lanczos basis?
Suppose that we are given a large, real-symmetric matrix $L$, which is simply too large to perform exact diagonalization on numerically. If we want to study its spectrum, one tool we can use is the ...
- 41
1
vote
1
answer
83
views
Powers of convergent DPR1 matrices in $O(d)$ time?
Suppose $u$,$v$ are vectors and $A$ is a convergent $d\times d$ diagonal + rank-1 matrix.
How do I estimate $u^T A^k v$ in $O(d)$ time?
Powers of convergent diagonal $D$ can be computed in $O(d)$ time ...
- 2,273
1
vote
0
answers
116
views
Which dense matrices are hard to invert?
Suppose I'm solving $Ax=b$ for dense $m\times d$ matrix $A$. For which $A$ is this hard to do?
More concretely, is there any work on estimating the error after $k$ steps of iterative solver, $k\le d$, ...
- 2,273
1
vote
0
answers
62
views
Does the choice of a complex inner product affect Krylov methods?
As far as I understand there are two definitions of the complex inner product:
$$(a,b) = b^H a$$
and
$$(a,b) = a^H b$$
I know some linear algebra libraries such as BLAS and Eigen uses the second one.
...
0
votes
1
answer
164
views
Can successive over-relaxation (SOR) method deal with ill-posed PDE BVP?
Recently, I've been struggling to understand the limitations and capabilities of the successive over-relaxation (SOR) method for boundary value problems which are ill-posed, such as, for instance, ...
- 53
1
vote
1
answer
230
views
Convergence stall when solving 2D Poisson PDE with pure Neumann boundaries (finite differences)
I recently started coding a small library of 2D PDE solvers (time dependent and time independent), and my first attempt was a 2D Poisson equation of the form:
$$\nabla(\epsilon\nabla\varphi)=\nabla\...
- 53
3
votes
3
answers
143
views
How to find the optimal SSOR parameter
The symmetric successive overrelaxation method features the iteration matrix
$$P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+U\right)$$
Either as a stationary ...
- 3,590
1
vote
0
answers
39
views
Solution to minimization problem when variables factor in 2 analytical problems
I am asking a follow up question to this question, but I could probably have written it as an answer instead. However, I don't know if what I am doing here makes sense or is too complicated for my ...
- 436
2
votes
1
answer
106
views
Iterative solution for a minimization problem involving matrix equations
I have a real valued function $F$ for which I am looking to find its global minimum. The function is well behaved and I can obtain its Jacobian. I could also compute the Hessian but the function ...
- 436
5
votes
2
answers
359
views
Recurrence relation for matrices
I have matrices ($S_0$ thought $S_N$) and I have a recurrence relation that link successive matrices together.
$$S_i + S_i(aS_{i-1}^{-1})S_i=C_i+aS_{i+1}$$
We can assume for this problem that $S_0=S_N=...
- 436
0
votes
2
answers
119
views
Eigenvectors of Laplacian
I am studying introduction to Multigrid methods.
In all tutorials, authors write that eigenvectors of Laplacian (1D, finite difference) are given as
$w_k(x_i) = \sin(k \pi x_i),$
where $x_i$ is a ...
- 13
1
vote
1
answer
82
views
Memory issues with iterative solvers
Was trying to implement a poisson 2d solver using Conjugate Gradient Method, so from 10x10 grid the matrix becomes 100x100 (since we have 100 nodes to find the values at), 100x100 grid goes to ...
- 384
3
votes
1
answer
1k
views
Solving Kepler's Equation with Newton-Raphson Method
Note (2022/03/07): This question is solved. Unfortunately, I'm not able to accept the correct answer by Lutz Lehmann, because I screwed up my registration and the account which posted this question is ...
2
votes
2
answers
90
views
Possible to use Iterative FD methods to solve a transformed non square domain [matlab]?
For the 2-D Poisson equation $$-(u_{xx}+u_{yy}) = f \ \ \text{where} f = 1$$
For boundary conditions
$$\frac{\partial u}{\partial n} = 0 \ \text{on AB and AD}$$
$$ u = 0 \ \ \ \text{on BC and CD no-...
- 23
1
vote
0
answers
73
views
Slow convergence of Stokes solver used with the Immersed Boundary method
I am using Immersed Boundary Method to simulate elastic particles in 3D Stokes flow. Specifically, one has $\nabla ^2 \mathbf{u}-\nabla p + \mathbf{f}(t) = 0$, $\nabla \cdot \mathbf{u} \; $, where $\...
- 21
4
votes
0
answers
51
views
Pass forward intermediate results during iterative optimization
To investigate a counter-current flow heat exchanger while considering temperature dependent physical properties (such as specific heat $c_\textrm{p,i}$, heat conductivity $\lambda_\textrm{i}$, ...
- 223
3
votes
1
answer
470
views
Incomplete Cholesky preconditioner for CG efficiency
I am currently solving the harmonic equation using a P1 FEM discretisation. The resulting matrix $A$ is SPD and fairly sparse so I use a preconditioned conjugate gradients (CG) solver to find a ...
- 1,271
3
votes
1
answer
526
views
When do not use preconditioners for sparse linear system of equations?
I'm implementing a solver of Finite Element Method, and to solve the linear system of equations I'm using gmres from MKL of Intel. Exists the option with and without a preconditioning. In what case it ...
- 515
0
votes
0
answers
84
views
Help with debugging block GMRES
I have written block version of GMRES by referring [1] and MATLAB implementation of gmres. I need to write it for complex matrices. My block implementation when run on single RHS is giving correct ...
6
votes
2
answers
151
views
Integrating exponential of second degree polynomials
I'm looking to compute the value of the following integral, for small values of $|a|$.
$$u_n(a,b)=\frac{1}{2}\int_{-1}^1 x^ne^{ax^2+bx}\mathrm{d}x$$
In this equation, $a,b \in \mathbb{R}$ and $n \in \...
- 436
3
votes
1
answer
326
views
Doubt regarding GMRES(m) and preconditioned GMRES
I have the two following algorithms for GMRES(m) and left preconditioned GMRES.
GMRES(m)
Left preconditioning
I would like to know if anyone could explain why steps 10 through 12 are not used in the ...
- 201
1
vote
1
answer
32
views
Find best matching ranges below limit in defined set of numbers
I am trying to calculate the best set of cuts for some wood cutting to reduce the waste.
So: Given a set of numbers, the goal is to find the best matches below a limit (size of wood beam).
Example of ...
- 111
4
votes
1
answer
134
views
Solving for a single element of a solution of a linear system
I wish to solve a linear system $A x =b$ in which $A$ is dense but not too large, say no larger than $10\times10$. However, I am not interested in the full solution vector $x = [x_0, x_1, \dots]$, ...
- 725
4
votes
0
answers
182
views
Stable iterative solver for complex symmetric linear systems
I am interested in the iterative solution (preferably Krylov-type solvers) of a problem $\boldsymbol{A}x=b$, with $x,b\in\mathbb{C}^{n\times1}$ and $\boldsymbol{A}\in\mathbb{C}^{n\times n}$. $\...
- 141
2
votes
1
answer
58
views
Simulate circular mold spread using cellular automata - square emerges instead
I am trying to simulate the spread of mold in a petri dish using a cellular automata based approach. Thanks to the answer in my other question Stochastic cellular automata - algorithm limited by 1 ...
- 197
4
votes
1
answer
104
views
Stochastic cellular automata - algorithm limited by 1 cell per timestep
Context
Let's say I am trying to model the spread of mold in a petri dish, using a stochastic cellular automata approach. The petri dish can be thought of as a grid of 1mm x 1mm squares, each called ...
- 197
0
votes
1
answer
175
views
Best search algorithm for optimal weight factor in SOR method
I had written an algorithm that searches for the optimal weight parameter to be implemented in the successive-over relaxation (SOR) method which worked cleanly by vectorizing the interval and for ...
- 169
3
votes
0
answers
189
views
How to obtain smallest eigenvalues with Arnoldi iteration
I understand that the Arnoldi iteration produces a basis which tends to include in its span the eigenvectors corresponding to eigenvalues of large magnitude (hence the analogy between the last vector ...
- 91
-1
votes
1
answer
57
views
relres in gmres MATLAB
I think the relres in MATLABis the form that relres = norm(M(b-Ax))/norm(M\b),when it smaller than tol then stop the iteration.
I want to know how to change relres to norm((b-Ax))/norm(b). Or use ...
- 1
7
votes
2
answers
229
views
solving linear system whose symmetrized matrix is positive definite
Are there iterative methods for the solution of nonsymmetric linear systems $Ax=b$ that can take (theoretical or practical) advantage from knowing that $A+A^T$ is positive definite? These matrices are ...
- 11.3k
0
votes
2
answers
293
views
Why minimizing with respect to A-norm?
Assume solving the linear system $A \textbf x = \textbf b$, with an $A$ so large that nothing but iterative methods may be employed. Assuming $A$ induces a norm, I realized that it is often desired to ...
- 21
1
vote
0
answers
36
views
Approximation in the derivation of the Arc Length method
I am studying the proof of the Arc Length method in section 2.2 of this thesis. In equation (2.2) the author introduces the supplementary conditions
$$
(\Delta {\bf u} + \delta {\bf u})^T \cdot (\...
- 255
3
votes
0
answers
155
views
Python routine to calculate shape resonances of H2
I am currently doing a project in which my aim is to write a program that can be used to calculate single and multi-channel shape resonances. So I'm looking at bound states and quasi-bound states.
...
- 31
-1
votes
1
answer
44
views
Automatic selection of the SLE solver and preconditioner during simulation
To simulate the physical process necessary to solve the arising systems of linear algebraic equations. The SLE matrix has a highly sparse form. There are a couple dozen non-zero elements in the string,...
1
vote
0
answers
151
views
Upper bound on condition number in linear preconditioning
I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite ...
- 11
2
votes
1
answer
376
views
Numerical Linear Algebra: When to use Direct methods versus iterative methods to solve a linear system - for PDEs in particular
I am reading the Chapra and Canale book on numerical methods, and was working through the chapters on solving linear systems. Now the book goes through direct methods including Gaussian Elimination, ...
- 287
1
vote
0
answers
35
views
Problem with recursive implementation of Subspace Iteration method in Numpy
I am having trouble with implementing the method of subspace iteration to find the eigenvalues and vectors of a random, symmetric matrix, A that is mxm with m = 10. ...
- 11
1
vote
0
answers
286
views
Minimax optimization with an oracle
I have an optimization problem of the following form: $$\min_y\left[\max_x f(x,y)\right].$$ It is fairly straightforward to minimize $f(x,y)$ over $y$ with $x$ fixed, and similarly to maximize $f(x,...
- 1,341
0
votes
1
answer
200
views
What are the advantages and disadvantages of using norm error control in the MATLAB ODE suit?
In MATLAB's ODE suit, there seem to be two basic methods of controlling the Local Truncation Error (LTE) of the ODE which the user can choose from, namely:
The absolute error control (default), ...
- 152
2
votes
1
answer
60
views
When will the Orthomin/CG iteration fails
I know that the the Conjugate Gradient iteration fails when $0\in \mathcal {W}(A^{H})$, which means there's a complex vector $x+iy$ such that $(x+iy)^{T}A^{H}(x+iy)=0$. I wonder how to derive a real ...
- 121