Questions tagged [linear-solver]

Referring to methods for solving linear systems of equations.

70 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
195 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{...
9
votes
0answers
266 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 ...
8
votes
0answers
95 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 ...
6
votes
0answers
126 views

What strategies / decompositions would be useful to solve the following linear system repeatedly if I only care about time to solution?

Let $A\in \mathbb{R}^{n\times n}$ be symmetric positive semidefinite, and $B\in \mathbb{R}^{n\times n}$ be symmetric positive definite. Suppose $B$ is block diagonal so it is easy to invert. (We ...
5
votes
0answers
95 views

Levinson Recursion for Non Square Toeplitz Matrices

Given a rectangular Toeplitz Matrix $ H $, how could one solve: $$ y = H x $$ For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $: $$ H = \begin{bmatrix} {h}_{1} & 0 & ...
5
votes
0answers
51 views

Nonlinear least squares optimized Jacobian calculation

I have a nonlinear least squares problem, in which I am trying to minimize residuals which can be divided into four classes: $$ \min_x ||\epsilon(x)||^2 + ||\xi(x)||^2 + ||\delta(x)||^2 + ||s(x)||^2 $$...
5
votes
0answers
502 views

Symmetric sparse direct solvers in scipy

scipy.linalg.solve, in its newer versions, has a parameter assume_a that can be used to specify that the matrix $A$ is symmetric ...
5
votes
0answers
351 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)$: $$ \...
5
votes
0answers
811 views

Can Gauss-Seidel/SOR (preconditioned?) be applied to a non-diagonally dominant matrix?

After applying finite difference method to a Laplace/Poisson problem always arises a diagonal dominant system of equations that can be solved with Gauss-Seidel or SOR methods. If the original PDE does ...
5
votes
1answer
246 views

Robust smoothers for geometric multigrid

I'm searching for robust smoothers for geometric multigrids. By robust I mean: Effective for high order approximations (say spectral element, spectral Discontinuous Galerkin), Parallel (suitable for ...
4
votes
0answers
56 views

Solving multiple linear regression in parallel

I am working on a problem where I need to solve approximately 500 Million Linear Regressions (OLS). What would be the most efficient way to do this (e.g. using GPU or a some framework that can do this ...
4
votes
0answers
83 views

hardware agnostic (GPU/CPU) sparse linear algebra C++ solvers framework/technology

I am looking for recommendations on matured C++ solver for Linear Sparse Algebra problems. The goal is to select between more or less GPU hardware agnostic libraries/frameworks that can be compiled on ...
4
votes
0answers
204 views

Once and for all: Which FEM plattform should I use for a very large multiphysics simulation?

I'm fooling around with the decision on how to build a multiphysics simulation for too long now (also several questions in this forum). First, I thought it would be possible/necessary to write most of ...
4
votes
0answers
156 views

How big a matrix can we row reduce in reasonable time?

I have very large matrices that I would like to row reduce (I need to keep track of the steps and find a basis of the kernel/image, not just find the rank). The good news is that I work mod 2 and the ...
3
votes
0answers
86 views

Stable iterative solver for complex symmetric linear systems

I am interested in the iterative solution (preferably Krylov-type solvers) of a problem Ax=b, with x, b ∈ ℂn x 1 and A ∈ ℂn x n. A is symmetric, invertible, and its real and imaginary parts are ...
3
votes
0answers
67 views

Kronecker-factored least-squares?

Suppose $a_i,b_i$ are $d\times 1$ matrices, $y_i$ is scalar, and I need to find least-squares solution $w$ of the following system of $n$ equations: $$y_i=(a_i^T\otimes b_i^T)w$$ Is there a ...
3
votes
1answer
106 views

Choice of iterative solver for a sparse asymmetric matrix with symmetric structure

I have a sparse $nxn$ matrix A with pretty interesting structure. It has a block structure with symmetric structure but asymmetric blocks. Expressed mathematically the block $A_{jk} = A_{kj}$ but $A_{...
3
votes
0answers
72 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 ...
3
votes
0answers
153 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 ...
3
votes
0answers
56 views

Preconditioning matrix with known spectrum

Assume I know all eigenvalues of a matrix $A$ fall into a certain set $\Omega \subset \mathbb{C}$. Is there any way I can exploit this knowledge to design a preconditioner for $A$? Some further ...
2
votes
0answers
90 views

Regularisation of ill-conditioned matrix-vector problem

I have a linear* problem which arises from an integro-differential system, and writes: $$ (\mathbf{I}+\lambda \mathbf{A})x = b $$ where $\mathbf{A}$ is a real full matrix, size $n\times n$, but is not ...
2
votes
0answers
39 views

"black box" preconditioner for shifted linear systems?

Does anyone know of any strategies for creating a preconditioner $P^{-1}_\sigma \approx (A+\sigma I)^{-1}$ given a preconditioner $P^{-1} \approx A^{-1}$, preferably such that the precomputation doesn'...
2
votes
0answers
158 views

Residual of Poisson equation with periodic boundaries

I am trying to write a multigrid solver for Poisson's equation, $-\Delta u=f$, on the unit square, $\Omega=(0,1)^2$ with periodic boundaries. My primary source has been Multigrid by Trottenberg, ...
2
votes
0answers
92 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 ...
2
votes
0answers
348 views

What algorithm do BLAS and ATLAS use for matrix multiplication?

I have searched and what I understood was that they use the naive one with several memory and cache optimizations. However, I wanted to know whether they are using the Strassen or the Coppersmith-...
2
votes
0answers
200 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
0answers
126 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
0answers
102 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,$$...
2
votes
0answers
228 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 ...
2
votes
0answers
61 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 ...
2
votes
0answers
104 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 ...
2
votes
0answers
263 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 ...
2
votes
0answers
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 ...
2
votes
0answers
264 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....
2
votes
0answers
795 views

Solving a system of 4 coupled PDEs representing variable diffusivity

I have four partial differential equations representing mass conservation of two compressible fluid phases (marked by subscripts $p1$ and $p2$) in two different continuum media (marked by subscripts $...
2
votes
0answers
99 views

Adaptive Mesh vs Uniform Mesh for multiple source/boundary/initial Data

I'm going to ask some beginners' questions. Adaptive mesh can save many DOFs than a uniform mesh. But it also needs to solve linear systems changing with mesh adaptive process. Is this not problem? ...
2
votes
0answers
127 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 ...
2
votes
0answers
218 views

Is it possible to run a Solver Foundation solver against a model containing linear and non-linear elements?

This is a follow up question to one I made previously about non-linear equations and ranged real numbers in Solver Foundation. I acknowledge that where possible, rewriting a problem that is non-...
1
vote
0answers
20 views

Comparing block versus non-block Krylov methods for handling multiple right-hand-sides

Suppose I wish to solve a linear system $AX=B$ iteratively where $A$ is an $m\times m$ matrix and $X,B$ are $m \times s $ matrices (not single vectors). Instead of solving $s$ independent systems I'm ...
1
vote
0answers
49 views

Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure

I am trying to use Newton's method to get a stationary solution for a system of equations of the following form: $$ \begin{Bmatrix} \frac{\partial x}{\partial t} \\ 0 \end{Bmatrix} = \begin{Bmatrix} f(...
1
vote
0answers
94 views

performance comparison between PETSc and SLATE

We want to start a new project to solve a large-scale inverse problem (O(10^6) number of parameters) to invert for subsurface wave speeds. We will use FEM to solve forward and adjoint PDEs. In our ...
1
vote
0answers
69 views

Convergence of Conjugate Gradient Algorithm

I am trying to solve a linear elasticity model using finite element discretization in a rectangle domain [0,1]x[0,1]. For the solution of the the linear system $Ku=F$ I am using the CG algorithm. ...
1
vote
0answers
289 views

Is there any function to calculate condition number of sparse matrix in Eigen libraray?

The function JacobiSVD and BDCSVD can calcuate condtion number of a dense matrix via singular values. However I need to know condition number of a sparese matrix due to slow computation speed using ...
1
vote
0answers
81 views

2-norm of solution update suddenly becomes zero after a few iterations

I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
1
vote
0answers
34 views

What kind of problem or matrices are suitable for multigrid method?

For Poisson or Convection-diffusion equation as follows: $$ -\Delta u=f,\qquad u|_\Omega = g. $$ or $$ -\Delta u +\vec{w}.\nabla u=f,\qquad u|_\Omega = g. $$ using FDM or FEM discretization, we can ...
1
vote
0answers
88 views

Hybrid Ellpack-Itpack (ELL) + COO Sparse Matrix Representation decomposition threshold

Hybrid ELL-COO sparse matrix representation can be done as in the picture, I was looking intensively, however I couldn't find out what is the threshold of decomposing the original matrix into ELL part ...
1
vote
0answers
105 views

implementation for coppersmith matrix multiplication

Is there any online implementation for the coppersmith matrix multiplication I have searched alot but can not find any? and if there is not any why is that Isn't this algotithm much faster than ...
1
vote
0answers
59 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 ...
1
vote
0answers
60 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
0answers
62 views

Parallel dense solve with submatrices from mesh refinement with Petsc

For a Bounday Element Method problem I require the solution of a system of linear equations with multiple right-hand sides. Though this is a dense system, I still want to do it via Petsc in parallel. ...