Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

Filter by
Sorted by
Tagged with
51
votes
4answers
7k views

What guidelines should I follow when choosing a sparse linear system solver?

Sparse linear systems turn up with increasing frequency in applications. One has a lot of routines to choose from for solving these systems. At the highest level, there is a watershed between direct (...
9
votes
1answer
2k views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
33
votes
3answers
14k 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 ...
21
votes
2answers
9k views

Libraries for solving sparse linear systems

There are a number of different libraries out there that solve a sparse linear system of equations, however I'm finding it difficult to figure out what the differences are. As far as I can tell there ...
6
votes
5answers
9k views

How to solve block tridiagonal matrix using Thomas algorithm

Thomas algorithm can be used to solve a tridiagonal matrix: $$ \begin{bmatrix} {b_ 1} & {c_ 1} & { } & { } & { 0 } \\ {a_ 2} & {b_ 2} & {c_ 2} & { } & { }...
7
votes
1answer
2k views

Solving for null space of a matrix with mkl LAPACK

I want to find a solution for $xA=0$, where $A$ is a square matrix. I know that most of the LAPACK routines solve for $Ax=b$. So I take $A^T$ as a, and set $b=0$. I have an additional restriction of $\...
6
votes
3answers
548 views

role of initial guess for iterative linear solver

Suppose we use a preconditioned iterative solver for a linear system. If the initial state for the solver can be chosen very close to the exact solution - does this reduce requirements for the ...
6
votes
3answers
4k views

How to find QR decomposition of a rectangular matrix in overdetermined linear system solution?

While trying to find cell-centered gradients in finite volume method computation of incompressible fluid flow I get over-determined linear system. This is a well known "cell based least-square" ...
3
votes
1answer
251 views

non-smooth convex c++ solver

I happened to know that there are advanced established techniques for non-smooth convex optimization in research. For example, these two papers: Nesterov, "Smooth minimization of non-smooth functions"...
3
votes
1answer
168 views

How many operations are needed for LAPACK's zgesv to solve a linear system?

I have a linear system of complex numbers. I am using LAPACK' zgesv (actually I am using intel MKL LAPACKE, but I am assuming the algorithm is the same). No assumption can be made about the system. I ...
12
votes
3answers
2k views

Sparse linear solver for many right-hand sides

I need to solve the same sparse linear system (300x300 to 1000x1000) with many right hand sides (300 to 1000). In addition to this first problem, I would also like to solve different systems, but with ...
6
votes
2answers
2k views

Solving Lx = b for big sparse Laplacian matrices

What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
5
votes
2answers
409 views

Solving Poisson equation with current BC using FEM

I have a 3-dimensional domain D, with 3 types of BC which I am trying to solve the Poisson equation on. $$-\nabla \cdot (\sigma(x,y,z)\nabla u)=0$$ Insulator (Neumann BC) Electrode set at some ...
3
votes
1answer
2k views

Iteratively solving 3D Poisson equation in MATLAB

I have written a function that sets up a sparse matrix A and RHS b for the 3D Poisson equation in a relatively efficient way. The set-up is nothing fancy: I have extended the 2D 5-point stencil to an ...
12
votes
2answers
6k views

solve $xA=b$ for $x$ using LAPACK and BLAS

I am porting an existing code from MATLAB to C++ and have a linear system to solve $xA=b$ (rather than the more typical form $Ax=b$) The matrix $A$ is dense, and of general form, but is no larger ...
10
votes
2answers
1k 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)$ (...
2
votes
2answers
232 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 ...
9
votes
2answers
1k 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 $1_n=(1,\dots,1)\in\...
8
votes
1answer
1k views

Solving system of linear equations with cyclic tridiagonal matrix

I have this problem in my textbook: Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} a_1&b_1&0&...
7
votes
1answer
137 views

What are some ideas to preprocess / precondition the following linear system?

Let $A\in \mathbb{R}^{n\times n}$ symmetric and positive semidefinite, and $\omega\in \mathbb{R}\setminus\{0\}$. I am interested in solving the following linear system for a range of values of $\...
7
votes
1answer
367 views

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix $B\in\...
7
votes
3answers
716 views

Solving shifted linear systems with LU factorization

I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization available....
6
votes
0answers
125 views

What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
5
votes
2answers
221 views

Solving “Hadamard systems”

Suppose we have two matrices $A$ and $B$ (we can assume they're symmetric; if absolutely necessary I think they may be positive definite). Then, is there any technique for solving $$(A\circ B)x=b,$$ ...
8
votes
0answers
183 views

Imbalance of variables in Mixing Newton's method and Linear solver for a Non-linear system

Problem Solving a non-linear system of equations. The number of variables is the same as the number of equations. When I fix a set of variables (say $\vec{y}$) and keep another set free (say $\vec{...
7
votes
1answer
518 views

Which preconditioning for large linear elasticity problem?

The problem I want to solve is the displacement formulation of the linear elasticity : $$ \nabla \cdot \sigma = 0 \quad \text{in} \quad \Omega \\ \sigma = \lambda ( \nabla \cdot u ) I + \mu (\nabla \...
5
votes
0answers
161 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 ...
4
votes
2answers
238 views

How “sparse” should a sparse matrix be to see benefits?

I have a matrix, whose size scales as $2^N$ (assume even $N$). In each row of the matrix, only about $2^{N/2}$ of the entries are filled ($N$ can be somewhere between 10 and 40, depending on what's ...
4
votes
2answers
189 views

How do the properties of a matrix affect the linear system solving

For a general matrix A, there are many properties to describe it: symmetric positive definite or indefinite, condition number, spectrum and so on. I am curious about how these properties affect the ...
4
votes
1answer
199 views

Choosing preconditioner for unsymmetric pressure-velocity coupled system

I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
3
votes
1answer
155 views

Derivatives of Approximate Matrix inverses

I am cross posting this question to the mathermatics stack exchange. please find it either at this link, https://math.stackexchange.com/q/2952989/430980, or below: I have a question concerning the ...
3
votes
2answers
210 views

Does length unit in FEM affect numerical condition?

I try to solve a system of coupled PDEs using FEM. Unfortunately, the originating matrix has very poor condition. After days of double checking and thinking, I suspect the following reason: Given a ...
2
votes
2answers
237 views

Automatic Differentiation - reverse accumulation of linear system solve

I am studying the reverse mode of automatic differentiation. The reverse mode of automatic differentiation allows the efficient computation of a the derivative of a single dependent variable $y$ with ...
0
votes
1answer
149 views

How to set an initial guess for the iterative solver in Comsol?

How to set the initial guess for the iterative solver GMRES or FGMRES for linear problems (Helmholtz equation of RF module) in Comsol?
0
votes
1answer
997 views

Is it possible to output the matrix condition number from pardiso (MKL)? [closed]

I am assuming the pardiso solver calculates (or estimates) the condition number before proceeding to the solution phase. Is there a way to make pardiso output the condition number? Alternatively, ...
0
votes
1answer
538 views

ZGETRF and ZGETRS from MKL - zgetrf fails and still zgetrs works?

I have a large system of equations $$Ax=b$$ and I know matrix $A$ and right-hand side vector $b$. I'm using MKL to solve this system. The matrices are complex. I have used the general solver ...