4
votes
0answers
44 views

Wanted: sequences of linear systems for recycling Krylov solver analysis

In the solution of sequences of linear systems $$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$ with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
2
votes
1answer
104 views

Question about extending Tikhonov regularization

I know that the Tikhonov regularization of a linear system has an analytical solution given by: \begin{equation} \hat{\mathbf{x}} = \mathrm{arg\;min}\left( \left| \mathbf{Ax} - \mathbf{b} \right|^{2} ...
2
votes
2answers
76 views

Advice on the regularisation of a linear problem

I'm numerically inverting an integral transform using a method suggested by a scicomp user from an earlier question. The problem is as follows: I wish to estimate $f(x)$ for a given $F(y)$, both of ...
2
votes
1answer
79 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 ...
2
votes
3answers
127 views

Sparse, underdetermined system of linear equations

I'm looking for an algorithm to solve the underdetermined system of linear equations $$\mathbf{A}\,\mathbf{x} = \mathbf{b}$$ with $\mathbf{A} \in \mathbb{R}^{n\times n}$, $\mathbf{b} \in ...
0
votes
0answers
19 views

Differences between methods for solving linear equation system [duplicate]

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several methods ...
2
votes
0answers
78 views

Lapack++ for QR algorithm

I have recently started using Lapack++ which I found convenient for my programming purpose, in general. Now, I need to solve a matrix using QR algorithm. I've searched the user manual and I found a ...
5
votes
1answer
124 views

What Linear Equation Solver should be used for a problem with many dirichlet conditions?

I am solving a laplace equation on a finite-element mesh (tetrahedral, triagonal) and have many say 99% dirichlet conditions compared to the number of unknowns. Is there an efficient way to solve this ...
6
votes
1answer
155 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
173 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 ...
4
votes
1answer
58 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: ...
2
votes
1answer
113 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 ...
7
votes
1answer
57 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 ...
4
votes
1answer
101 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 ...
9
votes
3answers
495 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 ...
0
votes
2answers
137 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 ...
3
votes
1answer
123 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 ...
0
votes
3answers
156 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 ...
2
votes
3answers
196 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 ...
8
votes
2answers
1k 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 ...
6
votes
3answers
317 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 ...
15
votes
3answers
430 views

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

I have matrices A and G. A is sparse and is nxn with n very large (can be on the order of several million.) G is an nxm tall matrix with m rather small (1 < m < 1000) and each column can only ...
4
votes
2answers
139 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 ...
11
votes
1answer
327 views

Projecting out the null-space of $A$ from $b$ in $Ax=b$

Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
3
votes
3answers
1k 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" ...
0
votes
3answers
213 views

Unique coordinates (solutions) in a single Gauss-Seidel iteration

I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices ...
3
votes
1answer
56 views

2D Jacobi line maintenance?

Suppose a linear system is given $$AX=B,$$ where $A\in\mathbb{R}^{n\times n}$ is a symmetric strictly diagonal matrix, and $X, B\in\mathbb{R}^{n\times 2}$. Therefore, the 2D Jacobi iterative solver is ...
7
votes
2answers
92 views

Initial guesses for perturbed linear systems

Suppose you solve a linear system $Au = f$ by an iterative method, e.g. conjugate gradients or Richardson iteration. Then you try to solve a linear system that is slightly perturbed in the matrix and ...
7
votes
2answers
764 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 ...
5
votes
1answer
385 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)$ ...
5
votes
2answers
255 views

Recommendation for a good article/book for frontal methods?

Can someone provide an article or book that explains the principle used in frontal solvers? Some examples also may help understand the frontal methods better.Thanks in advance!
3
votes
1answer
214 views

How to solve a problem with structure similar to a finite difference discretization of the 2D Poisson equation, but with non-symetric coefficients?

Recently, I've been asking about methods to solve a finite difference discretization of the 2D Poisson equation (see here and here) of the form: $$U_{i-1,j} + U_{i+1,j} -4U_{i,j} + U_{i,j-1} + ...
13
votes
2answers
2k 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 ...
31
votes
4answers
2k 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 ...