Referring to methods for solving linear systems of equations.

learn more… | top users | synonyms

0
votes
1answer
72 views

Fastest linear solver for sparse positive semidefinite, striclty diagonally dominant matrix

What is the state of the art for fastest linear solver for sparse, positive semi definite and strictly diagonally dominant matrix with N varies from ~700 to ~3000, and about a 1/16 of the matrix is ...
1
vote
3answers
77 views

Test set for linear solvers

Lets assume I have a iterative linear system solver, e. g. this one. Whats the typical approach on verifying and testing this kind of solvers? Is there a standard test set of linear systems one ...
0
votes
0answers
21 views

LaPlacian 3D example 34.c - how do you invoke multiGrid

I am having trouble running this code while exercising the ksp_type GMRES pc_Type mg -da_refine 1. Error Reports arguments are incompatible I read somewhere the pc_type MG works with all of the ...
2
votes
2answers
117 views

Solving Lx = b for big sparse Laplacian matrices

What algorithm is more practically suited in terms of performance for solving the $\mathbf{Lx=b}$ equation, where $\mathbf{L}$ is a generic Laplacian matrix (associated to a strongly connected graph, ...
2
votes
1answer
100 views

How do I simultaneously minimize two different functions who have the same inputs?

I want to minimize two different functions simultaneously who have the same inputs. The functions are both linear and non-exponential. $$F_1(X_1, X_2) = a_1X_1 + a_2X_2$$ $$F_2(X_1, X_2) = b_1X_1 + ...
3
votes
2answers
155 views

Solving linear system with 6 equations and 22 unknowns for six of the unknowns

I am trying to find the solution for the M variables in the following system. \begin{equation} 0 = C_{b} M^{b}_{x} - M^{a}_{x} k_{2a} + M^{a}_{y} \left(\omega - \omega_{a}\right)\\ 0 = C_{a} ...
1
vote
3answers
82 views

External solver in Abaqus/Ansys

Is it possible to call an external linear solver from Abaqus and/or Ansys? This solver (which is supplied by me) would get the sparse matrix A and the right hand side vector b as inputs, and would ...
11
votes
2answers
222 views

preconditioning a krylov method with another krylov method

In method like gmres or bicgstab it could be attractive to use another krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
1
vote
3answers
157 views

Surface normals integration

I am trying to reconstruct a 3D surface given the normals of the unknown surface. Reading through this paper on section 4 they say [...] denote the surface by $z(x,y)$. The directions of the ...
1
vote
0answers
84 views

How to solve sparse linear systems using CPUs and GPUs?

There are several libraries to (iteratively) solve large sparse linear equation systems in parallel on a number of CPUs. Our parallel cluster also has attached powerful GPUs, but so far, I did not ...
11
votes
2answers
205 views

Do black-box preconditioners for matrix-free methods exist?

Jacobian-Free Newton-Krylov (JFNK) methods, and Krylov methods in general, can be very useful because they don't require explicit storage or construction of a matrix, only the results of matrix-vector ...
2
votes
2answers
120 views

Does length unit in FEM affect numerical condition?

I try to solve a system of coupled PDEs using FEM. Unfortunately, the originating matrix has very poor condition. After days of double checking and thinking, I suspect the following reason: Given a ...
4
votes
1answer
132 views

Linear equation system: Direct solver works, iterative solver does not

I have to solve for x in b = A*x, where a is sparse. This works fine with Matlab's mldivide: x = A \ b. Since I will have to use an iterative algorithm for very large A, I'm currently testing Matlab's ...
1
vote
1answer
68 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 ...
8
votes
2answers
648 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 ...
3
votes
1answer
171 views

Large binary programming problem

I have 10000 variables (each of them is binary), vector of positive coefficients and a matrix A (10000*10000), if Aij is 1, then ith and jth variables can take 1 simultaneously, if it's 0, then it's ...
0
votes
1answer
54 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 ...
3
votes
3answers
131 views

Efficient solver for a symmetric tridiagonal system where the upper/lower diagonals are offset

I'm looking for an efficient way to solve a symmetric tridiagonal system $Mx = d$, where the upper and lower diagonals of $M$ are offset from the main diagonal by $k$ rows/columns: $$ \begin{bmatrix} ...
2
votes
1answer
66 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
5
votes
0answers
78 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 ...
1
vote
0answers
54 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? ...
3
votes
2answers
142 views

Solving Newton-Raphson step with ill-conditioned sparse matrix

I am trying to build a complex simulator for the transport of mass & heat in porous media. I am currently following coarsely the algorithm laid out in an older software and have got the simulator ...
3
votes
1answer
91 views

Updating an approximate solution to a linear system in response to a small change

This question was original posted on SO but it was suggested that I post it here. I'm working on a program in which I have a banded matrix M and a vector b, and I want to maintain an approximate ...
1
vote
1answer
101 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, ...
0
votes
1answer
50 views

How to use TrangularView class in Eigen C++

For a nonsingular lower or upper triangular square matrix $A$, how to solve such linear system in Eigen: $$A x = b$$
2
votes
1answer
108 views

Question about extending Tikhonov regularization

I know that the Tikhonov regularization of a linear system has an analytical solution given by: \begin{equation} \hat{\mathbf{x}} = \mathrm{arg\;min}\left( \left| \mathbf{Ax} - \mathbf{b} \right|^{2} ...
2
votes
2answers
77 views

Advice on the regularisation of a linear problem

I'm numerically inverting an integral transform using a method suggested by a scicomp user from an earlier question. The problem is as follows: I wish to estimate $f(x)$ for a given $F(y)$, both of ...
2
votes
1answer
110 views

full rank update to cholesky decomposition

Let $A$ be a real, symmetric, positive definite matrix. It has at least 500 rows, possibly much more. I compute its Cholesky decomposition, which allows me to calculate $det(A)$ $A^{-1}X$ for some ...
2
votes
1answer
74 views

Implicit Finite difference scheme for a PDE with only one boundary

I am looking at a few reaction-diffusion equations of the form $\frac{dP}{dt} = D\left(\frac{d^2P}{dr^2} + \frac{2}{r}\frac{dP}{dr}\right) - a(P)$ I know the initial conditions and the boundary ...
2
votes
3answers
144 views

Sparse, underdetermined system of linear equations

I'm looking for an algorithm to solve the underdetermined system of linear equations $$\mathbf{A}\,\mathbf{x} = \mathbf{b}$$ with $\mathbf{A} \in \mathbb{R}^{n\times n}$, $\mathbf{b} \in ...
0
votes
0answers
19 views

Differences between methods for solving linear equation system [duplicate]

I have a huge linear equation system in this form: F=K.Δ as usual form of problems in the finite element method, where the F vector and K are known and Δ vector is unknown. There are several methods ...
2
votes
1answer
100 views

How to re-use the coefficient matrix decomposition result when solving linear systems by Eigen C++

My problem needs to solve dense symmetric linear systems something like: A x = b, A y = x, ...
2
votes
1answer
39 views

What is the fomula of polynomial time of solving positive definite symmetric linear system

For a positive definite symmetric linear system, Cholesky decomposition based method should be the best solver which has a rough n^3/3 flops requirement. What is ...
3
votes
1answer
94 views

Constrained System / Combinatorial Problem

Let $x\in \mathbb{R}^{n}$, $Y\in \mathbb{R}^{mxn}$. We can then define: $row_{i}(Y)=$ $i^{th}$ row of $Y$ $column_{i}(Y)=$ $i^{th}$ column of $Y$ $x_{i}=i^{th}$ element of $x$ $sum(x)=$ sum of ...
3
votes
1answer
125 views

indirect method for least-squares with inequality constraints

I aim to find $x \in \mathbb{R}^n$ that $\min_x |D \cdot F \cdot x|^2$ subject to $x_i = X_i$ and $x_j \geq X_j$ , $i \in I, j \in J$ and I and J partition ${1\cdots N}$ into two sets. it is ...
3
votes
1answer
233 views

Solving for null space of a matrix with mkl LAPACK

I want to find a solution for $xA=0$, where $A$ is a square matrix. I know that most of the LAPACK routines solve for $Ax=b$. So I take $A^T$ as a, and set $b=0$. I have an additional restriction of ...
5
votes
1answer
298 views

Solving system of linear equations with cyclic tridiagonal matrix

I have this problem in my textbook: Suggest efficient algorithm for solving system of linear equations with cyclic three-diagonal matrix, that is of the form: \begin{bmatrix} ...
2
votes
1answer
133 views

Sparse linear solvers in C?

I'm working on translating a discontinuous Galerkin code from MATLAB to C and I'm at the final point where I need to solve a sparse system. I've taken a course in C before but I'm very rusty and ...
3
votes
1answer
83 views

Would recalculating the residual in the conjugate gradient method help?

The conjugate gradient method suffers from an accumulation of errors as it continues. For this reason it is unwise to use it as a direct solver. My question is, would it help to recalculate the ...
1
vote
2answers
124 views

Determine the step size in a differential equation numerical solver

How can we define the precision we require in a numerical differential equation solver? What is it that I have to optimize to know? And how do I know that I'm at a sufficient time-step value? For ...
3
votes
2answers
200 views

openmp update matrix from neighboring elements (parallelise preconditioner)

Issue of data dependency with stencil code... How to parallelise this using openmp? I looked at the openmp manual, I figured out how to use DO ORDERED to get the same result as the serial version, ...
4
votes
3answers
165 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D ...
3
votes
3answers
127 views

Pseudo-inverse of a discretized operator with a null space?

Is there a way to understand what happens when a singular operator is discretized and inverted using the pseudoinverse (say using the SVD Moore-Penrose pseudoinverse)? For example, if we discretize ...
2
votes
0answers
80 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 ...
3
votes
3answers
126 views

Smoothly varying dense matrices arising from computational science

I have written an algorithm to solve a dense system with smoothly varying entries. This means I assume there is no large jump from any entry to its neighbors. I would love to use ...
5
votes
1answer
130 views

What Linear Equation Solver should be used for a problem with many dirichlet conditions?

I am solving a laplace equation on a finite-element mesh (tetrahedral, triagonal) and have many say 99% dirichlet conditions compared to the number of unknowns. Is there an efficient way to solve this ...
3
votes
3answers
315 views

What is the best solver for solving a large sparse indefinite system

What's the best solver that can solve a large sparse but indefinite matrix?
3
votes
2answers
201 views

Memory management for solving large sparse systems with UMFPACK

I'm using umfpack for solving large systems of equation. However, I'm constantly getting out of memory issues for even modest size problems as pre2, torso3, ohne2 Hamrle3 (all from Tim Devis's ...
5
votes
2answers
376 views

What is linsolve() doing?

I'm converting a piece of matlab code to python but I am having difficulty recreating the solution it finds for an overdetermined sparse matrix. The original code used the overloaded left division ...
6
votes
1answer
171 views

Advice on solving a coupled physics problem

I am taking a shot at solving a coupled physics problem. I have this matrix formed: $\mathbf{J}=\begin{bmatrix} \mathbf{A} & \mathbf{B}\\ \mathbf{C} & \mathbf{D} \end{bmatrix}$ where ...