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.

Filter by
Sorted by
Tagged with
0
votes
0answers
25 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 ...
-1
votes
0answers
24 views

the convergence of the iterative algorithm has a major problem

In order to solve an optimization problem, I divided the main problem into two sub-problems. The two sub-problems require to be solved iteratively until the algorithm converges. I use the bi-section ...
6
votes
2answers
125 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 \...
1
vote
1answer
48 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 ...
1
vote
1answer
28 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 ...
4
votes
1answer
102 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]$, ...
3
votes
0answers
82 views

Stable iterative solver for complex symmetric linear systems

I am interested in the iterative solution (preferably Krylov-type solvers) of a problem Ax=b, with x, b ∈ ℂn x 1 and A ∈ ℂn x n. A is symmetric, invertible, and its real and imaginary parts are ...
2
votes
1answer
36 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 ...
4
votes
1answer
65 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 ...
0
votes
1answer
35 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 ...
2
votes
0answers
54 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 ...
-1
votes
1answer
32 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 ...
7
votes
2answers
168 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 ...
0
votes
2answers
145 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 ...
1
vote
0answers
31 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 (\...
3
votes
0answers
86 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. ...
-1
votes
1answer
34 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
0answers
74 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 ...
2
votes
1answer
131 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, ...
1
vote
0answers
23 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. ...
1
vote
0answers
277 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,...
0
votes
1answer
98 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), ...
2
votes
1answer
51 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 ...
3
votes
1answer
165 views

How to derive the simplified Newton iteration in the TR-BDF2 ODE integration scheme

The Problem The TR-BDF2 explained in this paper [1], is quite a popular numerical scheme used to integrate $\dot{y} = f(t,y)$, consistent of the following two stages: \begin{align} y_{n+\gamma} &...
1
vote
2answers
182 views

How can I color my Mandelbrot set like this?

I have a background image of a fractal on my phone that I would like in a higher resolution with super sampling, and decided to write my own program for it. I've got down rendering a Mandelbrot set, ...
3
votes
1answer
305 views

Calculating Error for Poisson Equation using Successive Over-Relaxation technique, Python

I am trying to solve the Poisson Equation $\frac{\partial^2 T}{\partial x^2} + \frac{\partial^2 T}{\partial y^2} = 32(x(x-1) + y(y-1))$ for a 61x61 grid using Python3 with boundary conditions being $T=...
6
votes
2answers
755 views

When is it easy to invert a sparse matrix?

(Crossposted on cstheory.SE) When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence ...
1
vote
0answers
260 views

Is there any function to calculate condition number of sparse matrix in Eigen libraray?

The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values. However I need to know condition number of a sparese matrix due to slow computation speed using ...
2
votes
3answers
385 views

On the reordering of sparse matrices

I have been reading on different techniques used to reorder sparse matrices to achieve better performance, the most popular being the Cuthill-McKee or Reverse Cuthill-McKee algorithm. Most of those ...
1
vote
0answers
81 views

2-norm of solution update suddenly becomes zero after a few iterations

I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
1
vote
1answer
44 views

Effecient method for iterating over sparse dataset

Apologies if this isn't the appropriate forum for this question. I have a set of elements that I need to iterate over as part of a modeling workflow. The elements exists over a set of dimensions (i, ...
1
vote
0answers
80 views

1-D Conduction Steady state heat transfer using FD

I have tried to solve 1-D Conduction Steady state heat transfer problems in Matlab (see below). Here is the 1-D model: T''[x] == 0, T[0] == 100, T'[100] == 0 ...
0
votes
0answers
63 views

The error in SOR algorithm suddenly falls to zero when it reaches 1e-7 range

I am solving the Poisson equation for heterojunction using Fortran90. I use the SOR algorithm to arrive at the potential profile. I see the weird behavior where the error (the difference between the $...
0
votes
1answer
107 views

Is it possible to predict solution oscillation before solving the system by looking at coefficient matrix?

Question When it is about solving a system of equations, is it possible to predict that whether high-frequency noise (e.g. checker-boarding) is likely to appear in the converged solution by looking at ...
2
votes
1answer
116 views

Project to nearest point on convex polyhedron

I have a point $y \in \mathbb{R}^d$ and a convex polyhedron $\mathcal{P}$ given as the intersection of half-spaces: $$\mathcal{P} = \{x \in \mathbb{R}^d \mid a_1 \cdot x \le b_1, \dots, a_n \cdot x \...
0
votes
0answers
64 views

Preconditioning the $[1 \quad-2 \quad 1]$ Finite Difference matrix

Let $A$ be the well known tridiagonal matrix coming from the 1D Finite difference discretization of the Laplacian, with stencil $\frac{[1 \quad-2 \quad 1]}{h^2}$. The system $Ax = b$ is very large, so ...
7
votes
2answers
338 views

Is there an iterative solver for dense matrices with possible zero diagonal entries?

Is there an iterative solver that can handle potentially zero entries on the central diagonal? I am implementing a polynomial fitting algorithm (up to $10^{th}$-order) and my matrix is a "...
1
vote
1answer
209 views

2D heat equation in both steady state and Transient state using iterative solvers

While solving a 2D heat equation in both steady-state and Transient state using iterative solvers like Jacobi, Gauss seidel, SOR. Should the answers, I mean the converged results of Temperature ...
4
votes
1answer
227 views

Without positive definiteness, does an iterative solver work?

Question Does lacking positive definiteness of the matrix of coefficients in a system of equations, make using iterative solvers impractical? Description Using the finite volume method, I have ...
0
votes
0answers
71 views

fixed point iteration on DD method

I have to solve the the problem $u_t+\Delta^2u=f(u)$, where $f(u)$ is non-linear, using domain-decomposition method. My approach is first using fixed point iteration on mixed form i.e to say $u^{k+1}...
4
votes
1answer
107 views

Why does smoothed aggregation multigrid method used as preconditioner in conjugate gradient slows down the solution time?

I'm solving a system of linear equations obtained from the FEM discretization of a simple linear elasticity problem on a cube with zero displacements at one plane and a load on the opposite one. The ...
2
votes
2answers
107 views

Solution of symmeric/non-symmetric linear system

I would like to understand what happens in the following: I have a really simple Poisson problem, in 1D, with $u_0 = u_N = 0$. I assembled the stiffness matrix and the right-hand side, and I applied ...
1
vote
0answers
78 views

Bifurcation points on homotopy path by numerical continuation?

I am trying to implement an algorithm that finds (possibly) all solutions of a system of nonlinear polynomial equations $$F(X) = 0$$ I thought about using the (convex) homotopy $$H(X,T) = TF(X) + (1-T)...
2
votes
1answer
57 views

Calculating coarse grid matrix in geometric multigird

The coarse grid matrix is calculated via RAP where R,P are the restriction and interpolation matrix,respectively.By checking a typical MG algorithm I want to ask how to calculate efficiently coarse ...
0
votes
1answer
53 views

Fixed-point iteration when image and domain are not the same

I have a function $f(x)$ defined on a domain $D$, but such that the image $f(D)$ may contain extra regions not included in its domain. I am interested in solving the fixed-point equation $x=f(x)$. If ...
4
votes
2answers
76 views

MInimizing cost function using iterative search for a minimum method

I want to estimated the parameters $\ \hat{\theta} $ of a model using an iterative search for the minimum of a cost function. The cost function is defined as follows: $$ V_N(\hat{\theta}) = \frac{1}{...
0
votes
1answer
356 views

How to implement the Hessenberg QR Algorithm?

For context, I'm creating a linear algebra library from scratch for learning purposes in C. Right now I'm working on calculating eigenvalues but my implementation of the QR Algorithm is diverging. ...
0
votes
0answers
76 views

Solving a nonlinear problem with a very small components with finite element method

In solving nonlinear hyperelastic solid mechanics problems, to converge to the correct solution we need to do step-by-step loading which makes the deformation at each step very small (for my ...
2
votes
2answers
157 views

What online optimisation algorithm can be used for a noisy cost function?

I am trying to optimise a function, but the function can be noisy and give varying results for the same parameters. Furthermore, it needs to be online, as the data from each new iteration happens ...
2
votes
1answer
132 views

Best way to check if SOR solution has converged for 2d matrix

I have written a SOR algorithm to solve the Laplace equation on a 2d grid. The outside of the grid is fixed at 0 and the central square is fixed at 10. I can obtain the fully converged solution for ...

1
2 3 4 5 6