All geek questions in one place

What is a quick simple solver for a large Laplace matrix?

I need to solve some large (N ~ 1e6) Laplacian matrices that arise when studying resistor networks. The rest of the network analysis is handled using the boost graph, and I would like to stay in C ++ if possible. I know that there are many, many C ++ matrix libraries, but no one seems to be a clear leader in speed or usability. In addition, many questions on this subject here and elsewhere seem to be quickly turning into lists of styles that have limited usefulness. In an attempt to help myself and others, I will try to keep the question brief and responsible:

What is the best library that can effectively meet the following requirements?

  • Matrix Type: Symmetric Diagonal Dominant / Laplacian
  • Size: very large (N ~ 1e6), no dynamic resizing required
  • Dexterity: Extreme (maximum 5 non-zero expressions per row / column)
  • Necessary operations: Solve for x in * x = b and mat / vec multiply
  • Language: C ++ (C ok)
  • Priority: speed and ease of coding. I would prefer to avoid having to learn a whole new structure for this one problem or manually write too much helper code.

Extra love for answers with a minimal working example ...

+4
source share
3 answers

Eigen is pretty nice to use one of the fastest libraries I know:

http://eigen.tuxfamily.org/dox/group__TutorialSparse.html

+2
source

If you want to write your own solver, in terms of simplicity, it is difficult to iterate through the Gauss-Seidel . The update step is one line, and it can be easily parallelized. Subsequent over-relaxation (SOR) is only a little more complicated and converges much faster.

Conjugate gradient is also easy to code and should converge much faster than other iterative methods. It is important to note that you do not need to form a complete matrix A, just calculate the matrix-vector products A * b. After that, you can improve the convergence rate by adding preconditions such as SSOR (Symmetric SOR).

Probably the fastest solution method that is wise to write is a Fourier-based solver. Essentially, this involves performing the FFT on the right-hand side, multiplying each value by a function of its coordinate, and adopting the inverse FFT. You can use the FFT library, such as FFTW , or flip your own.

A good reference for all of them is A First Course in Numerical Analysis of Differential Equations by Ari Aisers.

+2
source

There are many related posts you could look at. I would recommend C ++ and Boost :: ublas used in UMFPACK and BOOST's uBLAS Sparse Matrix

0
source

Source: https://habr.com/ru/post/1489061/

More articles:


All Articles