Tag Info

2

If you don't care too much about which $b$ you're working with (say just for linear algebra), then you can use the Method of Manufactured Solutions (MMS) in Linear Algebra much like we differential equations geeks would for our problems to start with a known exact solution, $x^*$, derive a $b$, and then apply your solver to see how decent an $x$ you can ...

4

I'd recommend a BLAS1/2-style implementation of LU decomposition with partial pivoting, along with forward/backward triangular solves. If you only have single digit numbers of unknowns, it should be fine to run dense/O(N^3) algorithms even on structured systems (ie banded/sparse/?). All these algorithms can be written in terms of "axpy" operations, ...

2

This question is as ill-posed as the matrices you may want to invert :-) Even the most complicated iterative methods, say GMRES to name an example, are not terribly difficult to implement and require only a couple of hundred lines of code. That's probably only a factor of 4 or 5 worse than the arguably simplest method, Richardson defect correction. But it is ...

5

For a single (maybe a few) $b$'s, I have found Conjugate Gradient can beat an $LL^T$ Cholesky factorization . To do this, I use MKL's Inspector-Executor sparse matrix-vector product mkl_sparse_d_mv with the following: a good re-ordering (COLAMD and METIS worked for me). This speeds up each matrix-vector product. To avoid a permutation operation each time, I ...

5

For problems this small, sparse direct solvers are faster than most iterative solvers even if you include the cost of factorization. As a result, I don't believe that you will be able to find a preconditioner for an iterative solver that can work in less than twice the cost of the forward-backward solve. You either have to pay the memory cost of a sparse ...

1

You can use Krylov iterative solvers with preconditioners. Since you mentioned that your problem of interest is linear elasticity, you end up with symmetric positive definite matrices, assuming that you use standard techniques. For this case, you can use the Conjugate Gradient method with the ILU preconditioner. These solvers are available in many languages. ...

0

I think there is a bit of jargon confusion here. So I will emphasize some words and the context I am using them. In NLA, when I attempt to solve a problem (they usually come from discretizations of PDEs), I know that the problem is well-posed, i.e. has a unique solution, beforehand. The problem may be ill-conditioned (opposed to well-conditioned) and that ...

1

There has been progress both in terms of the speed of computers (basically driven by Moore's law) and in the algorithms used to solve LP's and especially MILP's. Overall, improvements in algorithms have had at least as large an effect as improvements in hardware. How this will work out for your particular model is a different question. Especially for MILP'...

Top 50 recent answers are included