Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
326
questions
1
vote
0answers
57 views
Convergence of Conjugate Gradient Algorithm
I am trying to solve a linear elasticity model using finite element discretization in a rectangle domain [0,1]x[0,1]. For the solution of the the linear system $Ku=F$ I am using the CG algorithm. ...
0
votes
0answers
37 views
Open-source iterative solvers robust to noise?
I need to solve $Ax=b$ in about 1 million dimensions. Furthermore, A is only accessible through matrix vector products, and these are noisy/inexact.
Is there any solver with Python interface I can try ...
4
votes
1answer
114 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 ...
2
votes
1answer
40 views
Solving MX=N where M is structured as a Gaussian 4th-moment tensor
I'm looking to solve numerically the following equation for $(d,d)$ variable $X$, in Einstein summation notation
$$M_{ijkl}X_{kl}=N_{ij}$$
Where $M$ is a $(d,d,d,d)$ 4th-moment tensor of random ...
1
vote
0answers
56 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 ...
3
votes
1answer
90 views
Efficient solution to a structured symmetric linear system with condition number estimation
I have a real-valued linear system $Hx = b$ where $H$ is symmetric matrix** (not necessarily positive/negative definite) with a very particular structure:
$$
H = \begin{bmatrix} D && B \\ B^T &...
1
vote
0answers
51 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
2answers
110 views
How to use the Thomas-Algorithm to the Heat-diffusion-equation correctly
My post is structured in four parts:
I give you some information about the context my principal questions refer to.
I will tell you what I believe to know about the Thomas Algorithm. If I am wrong ...
0
votes
0answers
54 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
0answers
25 views
Abnormalities when using SOR to solve the Poisson Equation
I am trying to solve the Poisson equation for Heterostructures using SOR. The equation to solve looks lik
I have discretized the Poisson equation using finite difference and my code is written in ...
0
votes
1answer
98 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 ...
3
votes
1answer
84 views
Solve two-player game - minimize the l-infinity norm of a matrix-vector product
I have a matrix $M$ with non-negative real entries, and I would like to minimize the objective function
$$\Phi(v) = \|Mv\|_\infty,$$
where $v$ is constrained to be a probability vector, i.e., $v_1+\...
0
votes
0answers
54 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 ...
0
votes
1answer
93 views
Solving large sparse system
I am working on a problem with very large sparse matrices. I'd like to compute $A^{-1} B$, that is a crucial part of converting DAE to ODE (and there is no workaround). Here size of $A$ is 2E+5 x 2E+5 ...
1
vote
1answer
127 views
Efficient way to solve a set of linear equations $Ax=b$ when $A$ is sparse and some elements of $b$ are equal to zero
I have a set of linear equations, $Ax=b$. And about half of the elements in the right-hand side (vector $b$) are equal to zero. My system matrix $A$ is a sparse complex matrix. And $A$ is in the size ...
7
votes
2answers
266 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 "...
0
votes
0answers
49 views
Solver for large dense BVP system in python
I have a large system of boundary value problems of the form
$$ \frac{d^2 y }{dt^2} = C(t) y + b(t), $$
where the variable $y$ is a vector that has anywhere from 50 to around 500 components, $C$ is a ...
0
votes
1answer
61 views
Solving a sparse linear system using transpose of lower triangular matrix without copying
I have a sparse lower-triangular matrix $L$, and a right-hand side $b$, and I'd like to solve the linear system
$$L^T x = b$$
but without explicitly creating $L^T$. Ideally, I could write something ...
2
votes
1answer
90 views
Solving an m x m symmetric linear system involving a matrix multiplication versus an (n+m) x (n+m) system
Suppose that $R$ and $D$ are an $n \times m$ and $m \times m$ matrices. Assume that $m \ll n$ and that $D$ is positive definite. We would like to solve the system $(R^T R + D) x = R^T b$. This ...
3
votes
1answer
124 views
Is there any reason to scale a matrix before (sparse) Cholesky decomposition?
I have a sparse symmetric positive-definite matrix $M$ and I expect the entries in some rows/columns to have very different orders of magnitude (up to a factor of $10^8$) than the entries in others.
...
1
vote
2answers
193 views
Why OpenFOAM uses its own data structures and linear solvers?
I wonder why OpenFOAM code has its own data structures Lists, HashTables, ... etc. when there is the STL in C++?
Another ...
3
votes
1answer
110 views
What happens when I use a conjugate gradient solver with a symmetric positive semi-definite matrix?
I have a symmetric positive semi-definite matrix, i.e., a laplacian and wonder what may happen when I use a CG solver, that is an algorithm for positive definite matrices.
What happens when the ...
2
votes
2answers
85 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 ...
4
votes
2answers
140 views
More stable method of back substitution?
I've been tinkering a little in Fortran (2008) and wrote the following to solve
$Rx=b$ for $R\in\mathbb{R}^{n\times n}$ upper-triangular, $x,b\in\mathbb{R}^n$.
My code looks like this:
...
1
vote
1answer
72 views
Solving triangular matrix equations on a GPU
Suppose I have these two $N\times N$ lower triangular banded matrices:
$A = \begin{bmatrix}
a_0 & & \\
a_1 & a_0 & \\
a_2 & a_1 & a_0 \\
a_3 & a_2 & a_1 & a_0 \\
&...
1
vote
1answer
71 views
Parallel solution of PDEs
Which is the best approach to solve a PDE in parallel:
1.To split the mesh the mesh in N parts and every processor works on its own part or
2.To take the global linear system Ax=b and solve it in ...
3
votes
3answers
228 views
Using matrix exponential to solve linear system
Consider the system of linear equations:
$$
Ax=b
\tag{1}
\label{eq1}
$$
where
$A\in\mathbb F^{n\times n}$, diagonalizable dense matrix, over the field $\mathbb F$ of real or complex numbers,
$x\...
2
votes
1answer
117 views
How to solve for f(A)x=b without GMRES?
How to solve for $f(A)x=b$?
For GMRES, an answer is given in this book chapter: http://link.springer.com/chapter/10.1007%2F978-3-642-58333-9_2.
Ungated version:
https://www.researchgate.net/profile/...
2
votes
0answers
72 views
Residual of Poisson equation with periodic boundaries
I am trying to write a multigrid solver for Poisson's equation, $-\Delta u=f$, on the unit square, $\Omega=(0,1)^2$ with periodic boundaries. My primary source has been Multigrid by Trottenberg, ...
2
votes
0answers
72 views
Solving a huge least squares system of equations when I can only evaluate Ax
I have a situation where I can generate a system of $M$ linear equations for $N$ variables ($N \ne M$). Implicitly this is of the form $Ax=b$ with $A \in \mathbb{R}^{M \times N}$, although I never ...
1
vote
2answers
92 views
How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?
For the Krylov subspace method to solve the large sparse linear system, we first need to generate a subspace Km = span{v,Av,...A^{m-1}v}, which indeed a process ...
0
votes
0answers
104 views
How to implement the gmres method using Householder transformation instead of the Gram-Schmidt?
For Generalized Minimal Residual method GMRES, we usually use the Modified Gram-Schmidt MGS to generate an orthonormal basis of ...
3
votes
0answers
60 views
Levinson Recursion for Non Square Toeplitz Matrices
Given a rectangular Toeplitz Matrix $ H $, how could one solve:
$$ y = H x $$
For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $:
$$ H = \begin{bmatrix}
{h}_{1} & 0 & ...
2
votes
1answer
139 views
Testing a block tridiagonal system of equations
In 1D problems, tridiagonal systems of equations are obtained when we use finite-difference or finite-volumes in a structured mesh. A wide solver is the TDMA algorithm here. In two-dimensional ...
4
votes
0answers
46 views
Nonlinear least squares optimized Jacobian calculation
I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes:
$$
\min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2
$$...
4
votes
3answers
159 views
Solving for a vector in a linear system that is both left and right multiplied
I have a linear system where I am given 2 matrices, $A$ and $B$, and 2 vectors, $v$ and $c$, and I need to solve for the vector $x$. $A$ is $n\times n$, $B$ is $n \times n \times n$, and the vectors $...
2
votes
1answer
61 views
What is the standard, extrapolation, and modified version of Richardson iteration method?
I have been studying the iterative methods recently. For classical iterative methods solving $Ax=b$, I have seen that the most simplest iteration method is the so-called "Richardson iteration". But I ...
2
votes
1answer
91 views
What method to solve a sparse complex symmetric (non-Hermitian) system?
I have a sparse system (about 78% of zero entries) that is complex and symmetric (but not Hermitian). The following figure shows the structure of the problem. The off-diagonal blocks are incidence ...
2
votes
1answer
141 views
Why Krylov subspace iterative methods are faster than classical iteration?
This semester, I have been studying the most popular iterative methods, i.e., Krylov subspace iteration methods.
For a large sparse system linear
$$
Ax=b,
$$
where $A$ is nonsingular, I know that ...
1
vote
0answers
32 views
What kind of problem or matrices are suitable for multigrid method?
For Poisson or Convection-diffusion equation as follows:
$$
-\Delta u=f,\qquad u|_\Omega = g.
$$
or
$$
-\Delta u +\vec{w}.\nabla u=f,\qquad u|_\Omega = g.
$$
using FDM or FEM discretization, we can ...
0
votes
0answers
42 views
Why does the initial guess for linear system usually choose by zero vector?
For solving linear system
$$
Ax=b,
$$
using iterative mehods, we often use the terminate criterion as follows:
$$
\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}<eps.
$$where $x_0$ is the ...
2
votes
1answer
52 views
Partially Banded Matrix
I have a somewhat peculiar Jx=R system that I need to solve. The matrix J is 2N -by- 2N. The first N rows have all entries filled. The next N rows are banded in two places, i.e. for the (N+k)th row, ...
0
votes
1answer
61 views
Method to calculate solution of a linear equation system?
I am searching a solution method for the following equation system of equation systems:
Let $A, B \in \mathbb{R}^{n \times n}$ be s.p.d. Matrices and $O$ be the zero matrix of the same size. Further ...
5
votes
0answers
204 views
Symmetric sparse direct solvers in scipy
scipy.linalg.solve, in its newer versions, has a parameter assume_a that can be used to specify that the matrix $A$ is symmetric ...
1
vote
0answers
59 views
Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold
Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
1
vote
0answers
63 views
implementation for coppersmith matrix multiplication
Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
0
votes
0answers
179 views
What algorithm do BLAS and ATLAS use for matrix multiplication?
I have searched and what I understood was that they use the naive one with several memory and cache optimizations.
However, I wanted to know whether they are using the Strassen or the Coppersmith-...
1
vote
1answer
107 views
Lapack symmetric update $B^{-1}AB^{-T}$
Does Lapack have a routine that, given symmetric $A=A^T$ and $B$, computes the symmetric matrix $B^{-1}AB^{-T}$ (while preserving symmetry exactly)?
It would be enough to have this routine for ...
0
votes
1answer
94 views
The proper way to assess the error of Jacobi iteration (for 2D Poisson equation)?
Motivation: I'm using 2D regular grid (it's actually a quadtree but I can still treat it as a finite difference thing if I weight-average the solution over smaller scale cells for the purpose of ...
2
votes
2answers
276 views
Why iterative method: AMG preconditioned PCG is slower than Matlab direct method 'A\b'?
Recently, I have met a question that
a saying goes that for large linear system: iterative methods are required because of memory problem of direct methods.
But when I implement some experiments ...
