# Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

306 questions
Filter by
Sorted by
Tagged with
59 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 ...
114 views

Richardson's iteration introduce a scalar $\alpha$ to the update formula: $$\textbf{x}^{(k+1)} = \textbf{x}^{(k)} + \alpha \textbf{r}^{(k)}$$ And compute $\alpha$ by minimizing the spectral radius:...
119 views

### Efficiently solve linear system with matrix quadratic form

Take the system $$A^TCAx=b$$ where $$A\in\mathbb{R}^{n\times m},\;C\in\mathbb{R}^{n\times n},\;x,b\in\mathbb{R}^{m}, \;m\leq n$$ and $$A^TA=I$$ and $$Cy=d$$ can be solved efficiently in general (...
85 views

### Acceleration of matrix geometric series

Suppose we want to find $x$ such that: $$x=b+Ax$$ where $A$ is a large sparse square matrix with eigenvalues in the unit circle. There are two representations of the solution: 1) $$x=(I-A)^{-1}b,$$...
185 views

### Iterative linear solvers compatible with automatic differentiation?

I'm using automatic differentiation on a function that contains a sparse nonsymmetric linear system to be solved. I was using BiCGStab to solve this part of the function, but noticed the derivatives ...
52 views

### Scaling for a nonsymmetric eigenvalue problem

I have an eigenvalue problem emerging from the internal vibro-acoustic coupling. The eigenvalue problem is nonsymmetric but it was proven in literature that it results in real eigenvalues and ...
101 views

### Optimization based integration for MPM

I'm considering implementing (just for simplicity) the unconstrained implicit optimization based integration for Material Point Method as described in Chenfanfu Jiang's thesis on MPM (the minimization ...
197 views

### Fast solution of a heptadiagonal linear system

I have a linear system of the form $\mathbf{A}\mathbf{x} = \mathbf{f}$. If the length of the vector $\mathbf{x}$ is $N$, meaning that there are $N$ unknowns, then the matrix $\mathbf{A}$ has seven ...
81 views

### Solve for $D$ in $R^{T}DSDR = Id$

Given that $R$ is a rectangular matrix, $D$ is a diagonal, square matrix and $S$ being a square matrix along with the fact that both $D$ and $S$ are invertible. $S$ in this specific case can be ...
213 views

### Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?

I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
696 views

406 views

### Conjugate Gradient for non symmetric matrix

I have a large sparse matrix which is symmetric for the location of non zero values, but the values are different. Could I still use the CG method? I don't have much knowledge of linear algebra, the ...
117 views

I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results. In the statements of the propositions, what does it mean ...
201 views

### Fast counting of all submatrices of a binary matrix with a full column rank

I have a binary full-rank matrix of size, say, $25 \times 50$. I need to count how many subsets of its columns form matrices with a full column rank, i.e. all the columns in the subset are linearly ...
188 views

### Parallel linear algebra without OpenMP

I have searched through the archives without success. Apparently, the question is simple: What linear algebra library can I use that is parallel (shared memory) but without OpenMP? As far as I've ...
102 views

### Numerical method for solving a system with positive definite blocks

I have a system with below coefficient matrix $$C = \begin{pmatrix} A & B^T \\ B & D \end{pmatrix},$$ where, $A$ and $D$ are square and positive definite. Furthermore, if $B$ be square, ...
1k views

### Skyline solver for AX=B where A is symmetric skyline matrix

I am looking for a simple subroutine in Fortran 90 (GNU Compiler) to solve linear equation of the type $AX=B$, where $A$ is an $n\times n$ symmetric matrix stored in the form of symmetric skyline ...
316 views

### Solve steady state reaction-diffusion/Helmholtz equation numerically

I am solving a problem of the form: $\dfrac{\partial u(x,y,t)}{\partial t} = \nabla^2 u(x,y,t) - f(x,y,t)u(x,y,t) - \kappa(x,y,t)$ At the moment, I am solving this at each time step by assuming a ...
340 views

### Problem with convergence of Jacobi iterative algorithm

I'm dealing with Jacobi iterative method for solving sparse system of linear equations. For small matrices it works well and gives right answers even if matrix is not strictly diagonal dominant, ...
360 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 ...
248 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 (...
98 views

### Lapack symmetric update $B^{-1}AB^{-T}$

Does Lapack have a routine that, given symmetric $A=A^T$ and $B$, computes the symmetric matrix $B^{-1}AB^{-T}$ (while preserving symmetry exactly)? It would be enough to have this routine for ...
99 views

### Conjugate gradient - ill-conditioning and numerical tolerance

I would like to solve system $Ax=b$, where $A$ is SPD, but very ill-conditioned ($\text{cond}(A)>10^{11}$). I am interested in using UNpreconditioned version of the conjugate gradient method. Is ...
109 views

### Reordering algorithm for minimization of ram usage of a skyline matrix

The stiffness matrix of $Ax=B$ system of linear equations, where $A$ is an $n\times n$ symmetric matrix stored in the form of symmetric skyline matrix, that is associated with a finite element model ...
71 views

### Solving for $C$ in $Q = YCZ$ using least squares in Matlab

I am trying to solve for the matrix $C$ in $Q = YCZ$ in matlab. I have preliminary results but they don't seem realistic. Here, $Q$ is $n \times m-1$, $Y$ is $n \times p$, $C$ is $p \times m$ and $Z$ ...
337 views

### Algebraic multigrid in PETSc

Consider a potential/poisson equation on a very large, complicated geometry. Currently, an self-written FEM and linear solvers from NumPy are used. Performance is, of course, not good enough for ...
143 views

### How is the dense system usually dealt with in spectral method?

Unlike finite element (FEM) or finite difference methods (FDM), where the original PDE is transformed into a sparse linear system, spectral methods return a dense linear system. For a large system, it'...
149 views

### Difference between explicit and implicit preconditioning

What is the difference between an explicit and implicit preconditioner?
321 views

### How efficient (compared to “normal” methods) is using a sparse finite difference matrix to solve differential equations?

Any differential operator can be written as a finite difference matrix acting on a vector of values. I recently used it to solve $\Delta A = j$ by writing the Laplacian as a finite difference ...
327 views

### Solver library for matrix-free linear equation system

I will have to solve a large linear system. I'm now looking for a solver that works "matrix-free" (So that I just have to specify a matrix-vector product, but not the matrix). As far as I understand (...
89 views

### Least squares fitting

I have the following equation I came across which was solved using least squares $x = \sum_{n=1}^{N} A_{n} y_{n}$ Where $x$ is a $m \times p$ matrix and $y$ would be of size $m \times p$ as well ,...
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 ...
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 \\ &...