Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
4
votes
1answer
91 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
45 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
81 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 &...
10
votes
5answers
10k views

Best choice of solver for a large sparse symmetric (but not positive definite) system

I am presently working on solving very large symmetric (but not positive definite) systems, generated by some certain algorithms. These matrices have a nice block sparsity which can be used for ...
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+\...
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
104 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
53 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
94 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 ...
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 ...
1
vote
1answer
196 views

Method to solve linear, first order ODE of generalized matrix matrix form

The equation and its meaning: Consider two sets $(A)_{l=0,...,m_a},$,$(B)_{l=0,...,m_b}$ of hermitian matrices and a set of positive semidefinite matrices $(C)_{l=0,...,m_c}$. Each matrix has 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 ...
1
vote
1answer
118 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 ...
0
votes
1answer
92 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 ...
7
votes
2answers
263 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
2answers
190 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 ...
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
58 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
89 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
120 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. ...
3
votes
1answer
103 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 ...
4
votes
2answers
136 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
120 views

Evaluating a quadratic form with an inverse of a sparse PD matrix, comparison between using the inverse vs using a Cholseky decomposition

I have the following quadratic form I need to evaluate: $x^T A^{-1} y$, where $A$ is a sparse positive definite matrix, $x, y$ are sparse vectors. Now assume that I am given for free both $A^{-1}$ ...
1
vote
1answer
71 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 \\ &...
16
votes
2answers
781 views

Preconditioning a Krylov method with another Krylov method

In methods like gmres or bicgstab it could be attractive to use another Krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
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
227 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
69 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, ...
9
votes
4answers
520 views

fastest linear system solve for small square matrices (10x10)

I am very interested in optimizing the hell out of linear system solving for small matrices (10x10), sometimes called tiny matrices. Is there a ready solution for this? The matrix can be assumed ...
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
81 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
57 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 & ...
5
votes
1answer
145 views

Complex differentiation of linear solvers

I have a linear system $$Ax=b$$ which I'm solving approximately, and I need to take the frechet derivative of x with respect to z. Were I solving the problem exactly (either analytically or to machine ...
9
votes
1answer
3k views

Solving linear systems by fft

I read in a paper and also at wiki that we can solve the system $$Ax=B$$ by Fast Fourier Transform, where $A$ is a circulant matrix. The solution is $$x=\mathtt{ifft}(\mathtt{fft}(B)/\mathtt{fft}(a))$...
2
votes
1answer
131 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
3answers
156 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 $...
4
votes
0answers
44 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 $$...
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
87 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
138 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
31 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
51 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
184 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
58 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
2 3 4 5
7