Referring to methods for solving linear systems of equations.
4
votes
1answer
63 views
Solving linear systems by fft
I read in a paper and also at wiki that we can solve the system
$$Ax=B$$
by Fast Fourier Transform, where $A$ is a circulant matrix. The solution is
...
3
votes
0answers
29 views
Why do I get “estimated error” -1.#IND when doing BICGSTAB linear solver using ILUT perconditioner in eigen
I'm using Eigen (a C++ library for numerical linear algebra) to solve a linear equation with the the bi-conjugate gradient BICGSTAB algorithm with Incomplete LU preconditioner. However, the result ...
0
votes
1answer
34 views
Solver for sparse linearly-constrained non-linear least-squares [closed]
Reposted from stackoverflow:
Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and the solution is constrained with ...
1
vote
1answer
67 views
LU Decomposition with memory-mapped matrices
I have a ~4.12 Tb structured relatively-sparse matrix dataset (about 8% of the matrix entries are non-zero) that i want to apply an LU decomposition, however, given the size of it, loading it in ...
5
votes
1answer
166 views
Implementing Explicit formulation of 1D wave equation in Matlab
So the theory is straightforward. We have:
$$\frac{\partial^2U}{\partial t^2}=c^2 \frac{\partial^2U}{\partial x^2}$$
discretizing it gives:
$$\frac{U(i+1,j)- 2U(i,j) + U(i-1,j)}{(\Delta t)^2} = c^2 ...
11
votes
3answers
224 views
Problems where Conjugate gradient works much better than GMRES
I am interested in cases where Conjugate gradient works much better than GMRES method.
In general, CG is preferable choice in many cases of SPD (symmetric-positive-definite) because it requires less ...
5
votes
2answers
199 views
Solving a sparse and highly ill-conditioned system
I intend to solve Ax = b where A is complex, sparse, unsymmetric and highly ill-conditioned (condition number ~ 1E+20) square or rectangular matrix. I have been able to solve the system with ZGELSS in ...
2
votes
2answers
68 views
Problems where SPD linear system arises
I know some of the places where SPD linar systems arises such as elliptic PDEs and normal equations. Can I have a more comprehensive list of scientific applications which require solving SPD linear ...
3
votes
1answer
97 views
BFGS methods for constrained elasticity problems
My dear community,
I am wondering why BFGS methods are not so widely used for simulating mechanical problems which heavily still relies on inverting the hessian matrix. I am essentially interested ...
4
votes
1answer
120 views
Are there any specialized methods available for solving structurally symmetric sparse linear systems?
When solving $Ax=b$, prior knowledge about $A$'s structure can help in designing an efficient solver which exploits this information (e.g conjugate gradient method is to be used when $A$ is ...
3
votes
2answers
161 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} & { } & { ...
6
votes
1answer
45 views
Bad scaling versus collinearity
I was trying to solve a linear system:
$$
\mathbf{A}\mathbf{x} = \mathbf{y}
$$
but the conditioning number was quite bad (around $10^{17}$).
I thought that the system was singular, but after scaling ...
3
votes
1answer
176 views
in matlab, what differences are between linsolve and mldivide?
in matlab, both linsolve and mldivide are used for solving a system of linear equations, in all of determined, overdetermined and underdetermined cases.
Reading their documents, I was wondering what ...
6
votes
4answers
147 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 ...
0
votes
0answers
44 views
Memory errors with GSL ODE solver
I am trying to solve a (large) system of ODEs with GSL solvers. When I use driver method I get an error message of could not allocate space for gsl_interp_accel, ...
5
votes
3answers
180 views
Take advantage of the sparsity of b in AX=b
There is a lot of info about how to use the sparsity pattern of A in order to solve $Ax = b$. However I can't find much about using the sparsity pattern of b. Let me take a concrete example:
Let us ...
4
votes
1answer
62 views
Sparse LU for block-sparse matrices
I frequently need to solve linear systems with sparse matrices of moderate dimension (say a few thousand). These matrices are composed entirely of small dense blocks (typically 5-10 in dimension), and ...
5
votes
1answer
115 views
preconditioner for a matrix-free method to solve Ax=b
I need to solve Ax=b, but I realize that even if it is sparse, storing the matrix coefficients of my problem will take too much memory.
So now I'm considering using a matrix-free method, because the ...
6
votes
3answers
170 views
Sparse linear solver for many right-hand sides
I need to solve the same sparse linear system (300x300 to 1000x1000) with many right hand sides (300 to 1000).
In addition to this first problem, I would also like to solve different systems, but with ...
2
votes
0answers
51 views
Gaussian Elimination with partial pivoting
In Standard Gaussian Elimination, what modification constitutes "Partial Pivoting"? I understand that Gaussian Elimination implies that we start with the matrix and take a diagonal element, divide by ...
4
votes
3answers
96 views
Numeric solution of simple but possibly singular linear system
I have a simple (and small) linear homogeneous system $Ax=0$, where the entries of the $N\times M$ matrix $A$ are small integers. I do not need fancy methods which efficiently solve almost singular ...
0
votes
2answers
103 views
Checking for error in conjugate gradient algorithm
What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
5
votes
1answer
138 views
Using algebraic multigrid for preconditioning convection-diffusion operators
I implemented a Navier Stokes based on FEM discretization and PETSc for solving the linear system of equations. To create an efficient solution procedure, I follow the paper "Efficient preconditioning ...
3
votes
1answer
107 views
How do you formulate the linear least-squares method for radiometric calibration?
In Debevec and Malik (mentioned similarly in Forsyth and Ponce's Computer Vision: A Modern Approach) they highlight a method of solving the camera response function using linear least-squares.
We ...
7
votes
3answers
283 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$. ...
7
votes
3answers
280 views
Recommendations for a lightweight/no-install C or C++ based dense linear algebra solver
Most of my programming is one-off research codes in C for my own use. I have never distributed any code to other than close collaborators. I have developed an algorithm that I am publishing in a ...
8
votes
2answers
112 views
Efficient preconditioner for Augmented Lagrangian
I want to solve a non-linear problem with non-linear equality constrains and I'm using a augmented Lagrangian with a penalty regularization term that, as well known, spoils the condition number of my ...
0
votes
3answers
131 views
Equivalence of linear systems, solving one instead of the other
This question is related to recently posted one, but I guess it deserves a separate attention.
Suppose a symmetric matrix $L\in\mathbb{R}^{n\times n}$ is given, and a rectangular matrix ...
1
vote
3answers
153 views
Convergence of the gradient descent and linear vs non-linear fixed point iteration
Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can ...
6
votes
2answers
664 views
How to choose a method for solving linear equations
To my knowledge, there are 4 ways to solving a system of linear equations (correct me if there are more):
If the system matrix is a full-rank square matrix, you can use Cramer’s Rule;
Compute the ...
2
votes
2answers
209 views
Solving Poisson equation with free boundaries and adaptively refined mesh
Assume we want to solve the Poisson equation
$$
\Delta u = f
$$
with free (Neumann) boundary conditions. So, the right hand side function $f$ must fulfill the compatibility condition to integrate to ...
2
votes
3answers
232 views
derivative of linsolve
Consider a vector $\mathbf{g} \in \mathbb{R}^{m}$ and a matrix $\mathbf{A} \equiv \mathbf{A(g)} \in \mathcal{M}_{p\times q} [\mathbb{R}]$, a function of $\mathbf{g}$.
Furthermore, let $\mathbf{S} ...
5
votes
2answers
337 views
When to stop Gauss-Seidel-iterations?
I want to have an estimation, that my solution has an error, let's say less than 1e-8.
Usually, I stop the Gauss-Seidel algorithm, when the residual is "small enough" and this is already the problem. ...
8
votes
1answer
181 views
Solving huge dense linear system?
Is there any hope in solving the following linear system efficiently with an iterative method?
$A \in \mathbb{R}^{n \times n}, x \in \mathbb{R}^n, b \in \mathbb{R}^n \text{, with } n > 10^6$
...
0
votes
0answers
82 views
Is there a Mathematical Optimization API? [closed]
I mean something like:
I have to solve a Knapsack problem in my application
I describe an XML with all variables, objectives and more
I Upload this XML to a remote server (via a restful API)
I get ...
9
votes
3answers
513 views
Single versus double floating-point precision
Single precision floating point numbers take up half the memory and on modern machines (even on GPUs it seems) operations can be done with them at almost twice the speed compared to double precision. ...
6
votes
3answers
184 views
Wanting to learn about matrix solvers
Edit: I was advised to replace the question with a more specific one.
Coming from a very theoretical background, I'm pretty ignorant about what practical matrix solvers exist. (I have been, and will ...
4
votes
3answers
202 views
Solving shifted linear systems with LU factorization
I am interested in solving a sequence of shifted linear systems $(A+\sigma I)x = b$ for various values of $\sigma$. The matrix $A$ is sparse and not too large, so I have its LU factorization ...
5
votes
2answers
256 views
Taxonomy of ILU preconditioners
I learned that for BiCGStab solver for sparse linear systems it's pretty much always necessary to use a preconditioner. I realized by now that choosing a good one is problem dependent.
Surfing the ...
12
votes
3answers
367 views
Solving $(G^TA^{-1}G)x = b$ without inverting $A$
I have matrices A and G. A is sparse and is nxn with n very large (can be on the order of several million.) G is an nxm tall matrix with m rather small (1 < m < 1000) and each column can only ...
2
votes
0answers
36 views
Complexity of direct solvers? [duplicate]
Possible Duplicate:
How to reorder variables to produce a banded matrix of minimum bandwidth?
What is the time and space complexity of direct sparse solvers (e.g., UMFPACK, SUPERLU, ...
2
votes
0answers
103 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 ...
4
votes
2answers
126 views
How do the properties of a matrix affect the linear system solving
For a general matrix A, there are many properties to describe it: symmetric positive definite or indefinite, condition number, spectrum and so on. I am curious about how these properties affect the ...
10
votes
1answer
273 views
Projecting out the null-space of $A$ from $b$ in $Ax=b$
Given the system $$Ax=b,$$ where $A\in\mathbb{R}^{n\times n}$, I read that, in case Jacobi iteration is used as a solver, the method will not converge if $b$ has a non-zero component in the null-space ...
3
votes
3answers
520 views
How to find QR decomposition of a rectangular matrix in overdetermined linear system solution?
While trying to find cell-centered gradients in finite volume method computation of incompressible fluid flow I get over-determined linear system. This is a well known "cell based least-square" ...
5
votes
4answers
379 views
What are the best Python packages/interfaces to sparse direct solvers?
Please list the Python package (petsc4py, etc...) and the sparse direct solvers it supports. One (community-wiki) answer per package, please.
5
votes
1answer
226 views
How does a Sparse Direct Solver know about dimensionality of a problem being solved?
It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively.
But how does a ...
0
votes
3answers
186 views
Unique coordinates (solutions) in a single Gauss-Seidel iteration
I managed to reduce certain computational problem to the Gauss-Seidel solution of the following linear system: $$Ax=Ly,$$ where $A, L\in\mathbb{R}^{n\times n}$ are weighted Laplacian matrices ...
5
votes
2answers
189 views
How does matrix scaling influence linear solvers?
For instance, in MUMPS there is option to scale matrix s.t. all rows/columns have the same norm.
This claims to decrease condition number and improve numerical properties of the matrix: ...
3
votes
2answers
185 views
What numerical methods are recommendable for simulating two phase immiscible fluid flow through a pipe with high capillary pressure?
I'm simulating two phase immiscible drainage (air displacing water) in a rectangular domain of size .6mm x 2.4mm (2 dimensions) using Ansys FLUENT software. I am using an implicit Volume of Fluid ...
