Referring to methods for solving linear systems of equations.

learn more… | top users | synonyms

0
votes
1answer
46 views

Is it possible to output the matrix condition number from pardiso (MKL)? [closed]

I am assuming the pardiso solver calculates (or estimates) the condition number before proceeding to the solution phase. Is there a way to make pardiso output the condition number? Alternatively, ...
5
votes
1answer
82 views

Solving Generalization of Saddle point problem

I am interested in knowing if there is a generalization of the Uzawa iteration for the linear problems of the form $$\left[ \begin{array}{ccc}A& B^T&0\\ B&0&C^T\\ 0&C&0 ...
8
votes
4answers
146 views

Fast explicit solution for $\mathbf{A}\mathbf{x} = \mathbf{b}$, $ \mathbf{b} \in \mathbf{R}^3$, low condition number

I am looking for a fast (dare I say optimal?) explicit solution the 3x3 linear real problem, $\mathbf{A}\mathbf{x} = \mathbf{b}$, $\mathbf{A} \in \mathbf{R}^{3 \times 3}, \mathbf{b} \in ...
4
votes
0answers
92 views

Least-squares for a diagonal matrix

This is a follow-up to a different question I asked with more detail. For $v\in\mathbb{R}^n$, denote $D_v\in\mathbb{R}^n$ as the diagonal matrix with elements in $v$. Given a "tall" matrix ...
2
votes
3answers
117 views

Large overdetermined system of linear equations

I'm looking for a method to solve a large overdetermined system of linear equations in a least squares sense. The matrix is dense. I'd like to use a method that works even with limited memory (we ...
0
votes
0answers
26 views

Does cyclic reduction require a square mesh for 2D FEM/FDM?

In a 2-dimensional finite difference method or finite element method (triangular elements, each node is connected to 6 neighbors), each node has a matrix entry to its horizontal and vertical ...
4
votes
2answers
89 views

Solving “Hadamard systems”

Suppose we have two matrices $A$ and $B$ (we can assume they're symmetric; if absolutely necessary I think they may be positive definite). Then, is there any technique for solving $$(A\circ B)x=b,$$ ...
0
votes
1answer
80 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
81 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
31 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
122 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
102 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
156 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
100 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
227 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
92 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
210 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
124 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
134 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
71 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
699 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
190 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
138 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
67 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
81 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 ...
2
votes
0answers
55 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
152 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 ...
4
votes
1answer
98 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
54 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
123 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
75 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
149 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
22 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
105 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
95 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
134 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
247 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
329 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
137 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
84 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
127 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
203 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
177 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
132 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 ...