Questions tagged [linear-solver]
Referring to methods for solving linear systems of equations.
7
votes
0answers
64 views
How to construct an effective preconditioner for this particular problem
A quick introduction to my problem
I am currently developing a method for simulation of water waves in three dimensions based on potential flow theory. The computational bottleneck of the method is ...
1
vote
0answers
34 views
Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines
I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways.
One of these claims is that my proposed solution requires no explicit SVD and ...
2
votes
1answer
106 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, ...
6
votes
2answers
111 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-...
2
votes
1answer
67 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
0answers
59 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:...
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 ...
9
votes
3answers
320 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 ...
3
votes
0answers
63 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
108 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 ...
2
votes
2answers
113 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
81 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 ...
3
votes
1answer
447 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$...
1
vote
1answer
106 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 ...
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
83 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
85 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 ...
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 ...
8
votes
0answers
179 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{...
2
votes
2answers
122 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 ...
0
votes
1answer
51 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?
...
3
votes
1answer
123 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 ...
2
votes
2answers
217 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 ...
0
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
102 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 ...
2
votes
1answer
132 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 ...
6
votes
1answer
150 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 ...
4
votes
2answers
159 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
149 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)$:
$$ \...
1
vote
1answer
192 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 - \...
2
votes
0answers
105 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 (...
1
vote
1answer
74 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
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 ...
3
votes
0answers
103 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
89 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 ...
2
votes
2answers
193 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 ...
1
vote
1answer
154 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 ...
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
73 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,$$...
1
vote
1answer
148 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 ...
2
votes
1answer
102 views
Which iterative method and preconditioner from petsc should be used when solving linear algebra in parallel?
I am currently trying to parallelize the incompressible flow solver code.
However, when I run the code I realise that the parallel code takes much longer time than sequential code to finish one ...
1
vote
1answer
109 views
Questions about iterative projection methods in Saad book
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 ...
2
votes
1answer
160 views
MA57 vs HSL_MA57: symmetric indefinite solvers
What are the differences between MA57 and HSL_MA57 solvers? I'm in an optimization class that will make use of symmetric indefinite factorizations, and I'm trying to learn about the distinction ...
1
vote
0answers
58 views
Why do higher order finite elements (Q2) do not perform well for large Peclet number flows, as compared to Q1 finite elments?
I a solving the 2d steady state convection-diffusion problem on the famous flow around a cylinder in rectangular domain benchmark. My numerical results show that with Q1 finite elements, the solver is ...
1
vote
1answer
51 views
Optimal algorithm choice for mixed diagonal/dense problem
$$
\text{Let}\\
A, B \in \mathbb{C}^{n \times n} \text{ and } \hat{\alpha}, \hat{\beta} \in \mathbb{C}^{n}, \hat{f} \in \mathbb{C}^{2n}
\\
\text{Find }\\
\underline{\mathbf{x}} \in \mathbb{C}^{2n} \...
0
votes
1answer
58 views
Matlab backslash reordering algorithm
For the linear system $\mathbf A \mathbf x = \mathbf b$ generated from 2D Poisson equation using the standard central finite difference method,
$$
\mathbf A =
\begin{bmatrix}
\mathbf K & -\mathbf ...
0
votes
1answer
141 views
How to verify solution to pre-conditioned linear systems solver?
I am solving Ax=b. A has a very large condition number (> O(10^10))
I am using the conjugate gradients method with point jacobi pre-conditioning. I obtained a solution 'x' that "looks" reasonable. ...
2
votes
1answer
55 views
Implicit solution to Sylvester equation
Suppose a matrix $M\in\mathbb{R}^{n\times n}$ is defined as the solution to a Sylvester equation $$AM+MB=C,$$ for some fixed (known) matrices $A,B,C$. In the regime where $n$ is large, we may with ...
1
vote
1answer
70 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$ ...
1
vote
1answer
175 views
Method to solve linear, first order ODE of generalized matrix matrix form
The equation and its meaning:
Consider two sets $(A)_{l=0,...,m_a},$,$(B)_{l=0,...,m_b}$ of hermitian matrices and a set of positive semidefinite matrices $(C)_{l=0,...,m_c}$. Each matrix has the ...
