Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

6
votes
1answer
208 views

Advice on solving a coupled physics problem

I am taking a shot at solving a coupled physics problem. I have this matrix formed: $\mathbf{J}=\begin{bmatrix} \mathbf{A} & \mathbf{B}\\ \mathbf{C} & \mathbf{D} \end{bmatrix}$ where $\...
2
votes
1answer
1k views

Update QR decomposition when one column is exchanged

I have got an input series of matrices $A_1, A_2, A_3, \dots $ and the difference between $A_i$ and $A_{i+1}$ is the replacement of one single column. Before i get to know $A_{i+1}$, I have to ...
-1
votes
1answer
200 views

A question on CHOLMOD: long int vs int, still failing after change to long int [closed]

Changing cholmod_* to cholmod_l_* results in the following error: sparse:error: integer and real must match the routines ...
1
vote
1answer
480 views

What kinds of size of matrix A that CHOLMOD can solve Ax=b

CHOLMOD is very fast, but I am just wondering what kinds of size A such that it can solve Ax=b. I have a A of 200,000 * 200,000, but it outputs errors" problem too large". I am very appreciated if ...
2
votes
1answer
474 views

Sensitivity analysis of linear program with coin-or clp

I have written a short example to run the simplex algorithm with coin-or Clp, something quite simple like this: ...
4
votes
1answer
1k views

How to do transpose for trtrs (or tptrs) in blas?

How to do transpose for trtrs (or tptrs) in blas? I want to solve: XA = B But it seems that trtrs only lets me solve: ...
3
votes
3answers
501 views

Sources to get source codes for sparse matrix solvers (non-symmetric matrix)

For an implicit scheme I want to solve system $Ax=B$, where $A$ is a non-symmetric square matrix. I want source codes of large sparse matrix solvers (e.g. LU-SGS) to use in my code which is in C ...
7
votes
1answer
2k 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))$...
4
votes
1answer
162 views

Why do I get “estimated error” -1.#IND when doing BICGSTAB linear solver using ILUT perconditioner in eigen

I'm using Eigen (a C++ library for numerical linear algebra) to solve a linear equation with the the bi-conjugate gradient BICGSTAB algorithm with Incomplete LU preconditioner. However, the result <...
3
votes
1answer
275 views

LU Decomposition with memory-mapped matrices

I have a ~4.12 Tb structured relatively-sparse matrix dataset (about 8% of the matrix entries are non-zero) that i want to apply an LU decomposition, however, given the size of it, loading it in ...
5
votes
1answer
6k views

Implementing Explicit formulation of 1D wave equation in Matlab

So the theory is straightforward. We have: $$\frac{\partial^2U}{\partial t^2}=c^2 \frac{\partial^2U}{\partial x^2}$$ discretizing it gives: $$\frac{U(i+1,j)- 2U(i,j) + U(i-1,j)}{(\Delta t)^2} = c^2 \...
16
votes
3answers
3k views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD (symmetric-positive-definite) because it requires less ...
9
votes
3answers
4k views

Solving a sparse and highly ill-conditioned system

I intend to solve Ax = b where A is complex, sparse, unsymmetric and highly ill-conditioned (condition number ~ 1E+20) square or rectangular matrix. I have been able to solve the system with ZGELSS in ...
2
votes
2answers
134 views

Problems where SPD linear system arises

I know some of the places where SPD linar systems arises such as elliptic PDEs and normal equations. Can I have a more comprehensive list of scientific applications which require solving SPD linear ...
3
votes
1answer
565 views

BFGS methods for constrained elasticity problems

My dear community, I am wondering why BFGS methods are not so widely used for simulating mechanical problems which heavily still relies on inverting the hessian matrix. I am essentially interested ...
0
votes
1answer
423 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 ...
5
votes
2answers
219 views

Are there any specialized methods available for solving structurally symmetric sparse linear systems?

When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is ...
4
votes
5answers
8k 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
77 views

Bad scaling versus collinearity

I was trying to solve a linear system: $$ \mathbf{A}\mathbf{x} = \mathbf{y} $$ but the conditioning number was quite bad (around $10^{17}$). I thought that the system was singular, but after scaling ...
10
votes
1answer
13k views

in matlab, what differences are between linsolve and mldivide?

in matlab, both linsolve and mldivide are used for solving a system of linear equations, in all of determined, overdetermined and underdetermined cases. Reading their documents, I was wondering what ...
10
votes
5answers
8k 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 ...
1
vote
0answers
232 views

Memory allocation error with GSL ODE solver applied to system of 4 ODEs

I am trying to solve a (large) system of ODEs with GSL solvers. When I use driver method I get an error message of could not allocate space for gsl_interp_accel, ...
5
votes
3answers
271 views

Take advantage of the sparsity of b in AX=b

There is a lot of info about how to use the sparsity pattern of A in order to solve $Ax = b$. However I can't find much about using the sparsity pattern of b. Let me take a concrete example: Let us ...
4
votes
1answer
277 views

Sparse LU for block-sparse matrices

I frequently need to solve linear systems with sparse matrices of moderate dimension (say a few thousand). These matrices are composed entirely of small dense blocks (typically 5-10 in dimension), and ...
12
votes
2answers
5k 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 ...
12
votes
5answers
2k views

Repeatedly solving $\mathbf{A} \mathbf{x} = \mathbf{b}$ with same $\mathbf{A}$, different $\mathbf{b}$

I am using MATLAB to solve a problem that involves solving $\mathbf{A} \mathbf{x}=\mathbf{b}$ at every timestep, where $\mathbf{b}$ changes with time. Right now, I am accomplishing this using MATLAB'...
8
votes
1answer
1k views

preconditioner for a matrix-free method to solve Ax=b

I need to solve Ax=b, but I realize that even if it is sparse, storing the matrix coefficients of my problem will take too much memory. So now I'm considering using a matrix-free method, because the ...
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 ...
4
votes
3answers
166 views

Numeric solution of simple but possibly singular linear system

I have a simple (and small) linear homogeneous system $Ax=0$, where the entries of the $N\times M$ matrix $A$ are small integers. I do not need fancy methods which efficiently solve almost singular ...
1
vote
2answers
285 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
8
votes
1answer
522 views

Using algebraic multigrid for preconditioning convection-diffusion operators

I implemented a Navier Stokes based on FEM discretization and PETSc for solving the linear system of equations. To create an efficient solution procedure, I follow the paper "Efficient preconditioning ...
3
votes
1answer
189 views

How do you formulate the linear least-squares method for radiometric calibration?

In Debevec and Malik (mentioned similarly in Forsyth and Ponce's Computer Vision: A Modern Approach) they highlight a method of solving the camera response function using linear least-squares. We ...
14
votes
3answers
3k views

What are the symptoms of ill-conditioning when using direct methods?

Suppose we have a linear system and we know nothing about its conditioning and have no preliminary information about the solution. We blindly apply Gaussian elimination and obtain some solution $x$. ...
9
votes
3answers
1k views

Recommendations for a lightweight/no-install C or C++ based dense linear algebra solver

Most of my programming is one-off research codes in C for my own use. I have never distributed any code to other than close collaborators. I have developed an algorithm that I am publishing in a ...
12
votes
2answers
298 views

Efficient preconditioner for Augmented Lagrangian

I want to solve a non-linear problem with non-linear equality constrains and I'm using a augmented Lagrangian with a penalty regularization term that, as well known, spoils the condition number of my ...
0
votes
3answers
181 views

Equivalence of linear systems, solving one instead of the other

This question is related to recently posted one, but I guess it deserves a separate attention. Suppose a symmetric matrix $L\in\mathbb{R}^{n\times n}$ is given, and a rectangular matrix $A\in\mathbb{...
2
votes
3answers
811 views

Convergence of the gradient descent and linear vs non-linear fixed point iteration

Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can ...
29
votes
3answers
13k 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 ...
3
votes
2answers
585 views

Solving Poisson equation with free boundaries and adaptively refined mesh

Assume we want to solve the Poisson equation $$ \Delta u = f $$ with free (Neumann) boundary conditions. So, the right hand side function $f$ must fulfill the compatibility condition to integrate to ...
2
votes
3answers
398 views

derivative of linsolve

Consider a vector $\mathbf{g} \in \mathbb{R}^{m}$ and a matrix $\mathbf{A} \equiv \mathbf{A(g)} \in \mathcal{M}_{p\times q} [\mathbb{R}]$, a function of $\mathbf{g}$. Furthermore, let $\mathbf{S} \...
6
votes
2answers
3k views

When to stop Gauss-Seidel-iterations?

I want to have an estimation, that my solution has an error, let's say less than 1e-8. Usually, I stop the Gauss-Seidel algorithm, when the residual is "small enough" and this is already the problem. ...
11
votes
1answer
545 views

Solving huge dense linear system?

Is there any hope in solving the following linear system efficiently with an iterative method? $A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^n \text{, with } n > 10^6$ $Ax=...
6
votes
3answers
241 views

efficiently solving a low rank linear parametric systems?

I have a large number of systems of the form: $Ax=b_i$ To solve for a large numbers of such $b_i\;1\leq i \leq k$ but where $A$ is fixed (A is a rank $p$ general --i.e. non sparse, non PSD-- ...
12
votes
3answers
4k views

Single versus double floating-point precision

Single precision floating point numbers take up half the memory and on modern machines (even on GPUs it seems) operations can be done with them at almost twice the speed compared to double precision. ...
7
votes
3answers
239 views

Wanting to learn about matrix solvers

Edit: I was advised to replace the question with a more specific one. Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will ...
7
votes
3answers
626 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....
8
votes
2answers
1k views

Taxonomy of ILU preconditioners

I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent. Surfing the ...
22
votes
3answers
728 views

Solving $(G^TA^{-1}G)x = b$ without inverting $A$

I have matrices $A$ and $G$. $A$ is sparse and is $n\times n$ with $n$ very large (can be on the order of several million.) $G$ is an $n\times m$ tall matrix with $m$ rather small ($1 \lt m \lt 1000$) ...
2
votes
0answers
60 views

Complexity of direct solvers? [duplicate]

Possible Duplicate: How to reorder variables to produce a banded matrix of minimum bandwidth? What is the time and space complexity of direct sparse solvers (e.g., UMFPACK, SUPERLU, PARDISO, etc.)...
2
votes
0answers
214 views

Is it possible to run a Solver Foundation solver against a model containing linear and non-linear elements?

This is a follow up question to one I made previously about non-linear equations and ranged real numbers in Solver Foundation. I acknowledge that where possible, rewriting a problem that is non-...