Stack Exchange Network

Stack Exchange network consists of 175 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.

0
votes
0answers
38 views

A fast way to check if a Matrix is ill-conditioned, and turning it into well-conditioned

I'm running a simulation, and some linear solvers are returning a message of ill-conditioned matrix. Hence, I'm looking for a fast, easy to implement, method to detect if a matrix is ill-conditioned, ...
0
votes
0answers
49 views

Implementation of flexible inner-outer GMRES

I would like to implement a flexible GMRES version using the GMRES itself as a preconditioner as suggested in these papers Saad and Simoncini. Having a linear system like $$ Ax=b$$ The algorithm ...
6
votes
2answers
107 views

Efficient approach for solving matrix plus diagonal matrix system that varies in time

When solving a system of ODEs, as part of a preconditioner, I get the system $(A + D(t))x = b(t)$ where $A$ is a sparse matrix and $D(t)$ is diagonal. I'm currently solving this by taking the LU-...
1
vote
1answer
63 views

Assessing numerical error in solving a least squares problem

I have a linear system of the type $$Ax = b$$ I want to minimise $|b - Ax|^2$. I know there are different approaches to directly solve the system (Normal equation + Cholesky, QR decomposition, SVD ...
2
votes
1answer
56 views

Right-preconditioning and fixed point linear iterations

Given a linear system $A\textbf{x}=\textbf{b}$, we can express it into the easier-to-solve right-preconditioned form: $$ AM^{-1}\textbf{y}=\textbf{b}, \quad \textbf{y}= M\textbf{x} $$ On the other ...
2
votes
0answers
45 views

Richardson's Iteration, Gradient Method and Spectral Radius

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:...
9
votes
3answers
315 views

fastest linear system solve for small square matrices (10x10)

I am very interested in optimizing the hell out of linear system solving for small matrices (10x10), sometimes called tiny matrices. Is there a ready solution for this? The matrix can be assumed ...
1
vote
3answers
243 views

Practical reference on sparse linear solvers for PDEs (Navier-Stokes, Poisson) and on learning PETSc

My background is mainly engineering and applied research and I have been a developer or some CFD software, but mostly at high level without worrying about linear solvers and the like. This has been ...
2
votes
0answers
61 views

Numerical analysis, pivoting and incomplete LU decomposition

When doing LU decomposition, the algorithm will break down if any of the diagonal element $x_{ii}$ is zero. Therefore, we can use pivoting on the matrix such that $x_{ii}$ is no longer zero. That is ...
6
votes
1answer
105 views

numerical solution of an under-determined linear equation in high dimensions

I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
3
votes
1answer
126 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 ...
2
votes
2answers
103 views

Asymptotic Complexity of Gaussian Elimination using Complete Pivoting

I would like to know the algorithm asymptotic complexity with Complete Pivoting. With partial pivoting, it is known to be $O(n^3)$. Is it the same for complete pivoting?
1
vote
1answer
76 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 ...
2
votes
1answer
252 views

Which C++ linear algebra library is probably the fastest on solving huge sparse [square matrix] linear system?

I am developing a 2D CFD solver for fluid-particle interaction. To solve Navier-Stokes equations on a grid of size $10000\times 10000$ cells (or >1 million cells), a large linear system $Ax=b$ with $A$...
13
votes
3answers
3k views

Is the Thomas algorithm the fastest way to solve a symmetric diagonally dominant sparse tridiagonal linear system

I am wondering if the Thomas algorithm is the fastest way (provably?) to solve a symmetric diagonally dominate sparse tridiagonal system in terms of algorithmic complexity (not looking for ...
1
vote
1answer
75 views

Memory and time requirements of the scipy sparse spsolve

I have a system of fairly large set of linear equations (approximately 30K equations). I am using scipy.sparse.spsolve to solve these equations. Initially, I tried ...
8
votes
0answers
178 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{...
0
votes
1answer
36 views

Can LINCS algorithm be used for colliding molecules?

Supposing that one molecule is static and one is dynamic, can the dynamic one be solved with LINCS for its shape (angle, bond length) constraints and also keep collisions with static molecule off, ...
2
votes
1answer
81 views

Is steady linear elasticity inherently ill-conditioned?

Compared to the transient PDE for linear elasticity, the steady equations appear to less well-conditioned. Are they inherently ill-conditioned without the transient term? The condition number for ...
3
votes
1answer
74 views

Condition number of matrix and effects of round off errors

In my numerical linear algebra class, I learned that for some matrices, it could have an element that is a very small number that is approximately 0 (and many orders of magnitude different from all ...
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} & { } & { }...
3
votes
2answers
117 views

Memory/speed tradeoff for many small matrix inverses

Problem In the case of a finite element code, I have many small (order of 30x30) matrix inverses (or LU factorizations), one per finite element. These matrix inverses never change and must be applied ...
-1
votes
1answer
47 views

How to access solution to linear system in PETSc?

I have just started with PETSc hence it might seem like a very stupid question but I couldn't find any answer in manual. After Calling KSPSolve, where can I access the soluition for my linear system? ...
10
votes
2answers
956 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)$ (...
3
votes
1answer
120 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 ...
1
vote
1answer
72 views

Partitioning SPD matrix with METIS to preserve block SPD-ness

I am using the METIS to partition a matrix and then using domain decomposition to solve the subdomains in parallel using the Restricted Additive Schwarz method. I am currently trying to solve some ...
2
votes
2answers
197 views

Lost on Matrix Inversion

I try to implement some big matrix inversion. My system configuration is Hardware:- Memory: 62.8GiB, Processor: Intel Xeon(R)CPU E5-2670 v3 @2.30GHZ*48 To implement matrix inversion I am using ...
10
votes
5answers
9k 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
votes
1answer
83 views

Use of GPU with respect to CPU

I have research work where I need to compute a matrix inversion. The matrix has a size $31300\times31300$. I am using a universal java matrix package to invert this matrix. But as the dimension of the ...
2
votes
1answer
128 views

Can the Power Method be used here?

Given a set of $n$ points on which a triangulation is performed, it is possible to construct coefficients $\lambda_{ij}>0$ such that each point $x_i$ is a convex combination of the points connected ...
3
votes
1answer
89 views

How can a CG solver solve a non positive definite sparse matrix

I am using the CUSP CG solver and I ran it on couple of sparse matrices from the University of Florida sparse matrix collection. The solver was able to solve non positive definite sparse matrices. My ...
6
votes
1answer
147 views

Solving linear system of the form $ABx=b$

I would like to solve a linear system of the form $ABx=b$ in parallel, where $A$ and $B$ are large, sparse matrices. Currently, I am forming the system matrix $AB$ explicitly, but I would like to ...
1
vote
1answer
188 views

How to use CSDP to express a semidefinite program?

I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program $$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
4
votes
2answers
149 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 ...
5
votes
0answers
130 views

conjugate gradient for Newton's method with non positive definite Hessian matrix

I want to minimize a non-linear function $f(x)$ using Newton's method. At each optimization step, I compute a descent direction $d$ to update $x$ using a second-order approximation of $f(x)$: $$ \...
0
votes
1answer
932 views

MATLAB: code for restarted gmres

I have a question about Matlab and restarted gmres. I would like to use gmres.m provided here. This code seems to be popular for the scientific computation newcomer....
14
votes
3answers
4k 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$. ...
2
votes
0answers
101 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 (...
2
votes
1answer
121 views

Finite Elements: using preconditioned conjugate gradients with incomplete cholesky decomposition

I have to write a little finite elements code in C. I was asked to implement the conjugate gradients method, which I have done. Now, I am looking to improve further the efficiency of my program by ...
2
votes
2answers
191 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 ...
3
votes
0answers
101 views

Iteratively solving a sparse, ill-conditioned system

I have a sparse (density = 0.2%), ill-conditioned system that I am trying to solve, with no luck. Background I have a sequence of sampled data, where two of every 8 samples have been zeroed due to a ...
1
vote
1answer
84 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 ...
3
votes
1answer
254 views

Finding Interior eigenvalues using Davidson algorithm

Is it possible to find interior eigenvalues closer to some lambda using Davidson method. I was searching online but found that most people use Jacobi-Davidson method for that. Thanks
1
vote
1answer
123 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 ...
-1
votes
1answer
202 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 ...
3
votes
1answer
101 views

Solve $A^{-1} b$ when one column is replaced

Given square matrix $A_0$, vector $b$, vector $A_0^{-1}b$ and matrices $A_1, A_2, \dots, A_k$, in which each $A_i$ is generated from $A_{i-1}$ by replacing one single column, I would like to find an ...
2
votes
0answers
71 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,$$...
3
votes
1answer
114 views

Suggestions for an out-of-core sparse solver

I have a sparse $2\times10^5$ by $2\times10^5$ matrix with $3.2\times10^9$ non-zero elements. I want a sparse solver with out-of-core functionality. I have attempted to use Intel's ...
1
vote
0answers
55 views

bound error for iterative method for solving linear system

$A$ is square and positive definite, and let $r_k = Ax_k - b$. Also let $M = \frac{1}{2}(A+A^T)$. I want to show that $$\frac{||r_{k+1}||_2}{||r_k||_2} \le \left(1-\frac{\lambda_\min(M)^2}{\lambda_\...
1
vote
1answer
146 views

Efficiency of parallel direct linear solver

I am currently working on solving a positive definite symmetric systems in parallel. The parallel direct solver I used is MUMPS. However, the performance and efficiency of the parallel direct solver ...