Tagged Questions

1
vote
1answer
66 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 ...
6
votes
1answer
45 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
62 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 ...
0
votes
2answers
102 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
107 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
131 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 ...
1
vote
3answers
153 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 ...
6
votes
2answers
660 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 ...
4
votes
3answers
202 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 ...
12
votes
3answers
367 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
126 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 ...
10
votes
1answer
270 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
519 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
184 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
51 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 ...
6
votes
2answers
82 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 ...
6
votes
2answers
598 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
264 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
178 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!
2
votes
1answer
179 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} + ...