4 ms·

HODLR: Fast direct solver and determinant computation for dense linear systems

69 points by sndean 9y ago

petters 9y ago
For matrices of the form s^2 I + B, where B(i, j) depends on the distance between points i, j.
stabbles 9y ago
I believe state of the art methods aim for linear time complexity, using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2), and applying that in an iterative solver such as GMRES, which typically requires a constant number of iterations, because the matrix is just a slight perturbation of the identity matrix.
- Someone 9y ago
  "using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2)" If that's generic, couldn't we do matrix-matrix multiplication in O(n^2)? So, what are the limitations on that?
  - pkhuong 9y ago
    The results are approximate (but that's always true), and, IIUC, the quality of the approximation depends on how well the matrix can be factored into a local component (with values inversely proportional to |(i - j)|) and a sparse global component. Like petters writes above, "matrices of the form s^2 I + B, where B(i, j) depends on the distance between points i, j." The GMRES + FMM approach is more general, but FMM is less and less Fast as we move away from the structure above towards general matrices. This structure makes sense because it reflects physical reality… useful in when solving physics problems (: Less so when the matrix corresponds to logical/business constraints over 0/1 variables which may not be so local anymore.
nailer 9y ago
Could someone with the appropriate CS background give a summary for layperson programmers? I understand matrices and transforms but what is 'solving' them?
- IshKebab 9y ago
  Suppose you have an equation Ax = b, where A is a matrix and x and b are column vectors. If you know A and b, solve for x.
  - jey 9y ago
    And usually you should just use an LU factorization of A to do that. This HODLR library only applies in some rare circumstances.
deleted 9y ago
[deleted]
chrispeel 9y ago
Tangentially-related silly trivia: in cryptocurrency circles, a 'hodlr' is someone who is committed to a long position. I.e. who is 'holds' the cryptocurrency with the idea that in the long (perhaps very long) term it will be more valuable. The term comes from a misspelling of 'hold' by a drunk poster to bitcointalk [1]. [1] https://www.reddit.com/r/Bitcoin/comments/2b8t78/whats_hodl/ https://www.reddit.com/r/Bitcoin/comments/2b8t78/whats_hodl/

69 points by sndean 9y ago

For matrices of the form s^2 I + B, where B(i, j) depends on the distance between points i, j.

I believe state of the art methods aim for linear time complexity, using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2), and applying that in an iterative solver such as GMRES, which typically requires a constant number of iterations, because the matrix is just a slight perturbation of the identity matrix.

Someone 9y ago
"using the Fast Multipole Method to perform matrix-vector products in O(N) operations rather than O(N^2)" If that's generic, couldn't we do matrix-matrix multiplication in O(n^2)? So, what are the limitations on that?
- pkhuong 9y ago
  The results are approximate (but that's always true), and, IIUC, the quality of the approximation depends on how well the matrix can be factored into a local component (with values inversely proportional to |(i - j)|) and a sparse global component. Like petters writes above, "matrices of the form s^2 I + B, where B(i, j) depends on the distance between points i, j." The GMRES + FMM approach is more general, but FMM is less and less Fast as we move away from the structure above towards general matrices. This structure makes sense because it reflects physical reality… useful in when solving physics problems (: Less so when the matrix corresponds to logical/business constraints over 0/1 variables which may not be so local anymore.

nailer 9y ago

Could someone with the appropriate CS background give a summary for layperson programmers? I understand matrices and transforms but what is 'solving' them?

IshKebab 9y ago
Suppose you have an equation Ax = b, where A is a matrix and x and b are column vectors. If you know A and b, solve for x.
- jey 9y ago
  And usually you should just use an LU factorization of A to do that. This HODLR library only applies in some rare circumstances.

deleted 9y ago

[deleted]

chrispeel 9y ago

Tangentially-related silly trivia: in cryptocurrency circles, a 'hodlr' is someone who is committed to a long position. I.e. who is 'holds' the cryptocurrency with the idea that in the long (perhaps very long) term it will be more valuable. The term comes from a misspelling of 'hold' by a drunk poster to bitcointalk [1]. [1] https://www.reddit.com/r/Bitcoin/comments/2b8t78/whats_hodl/ https://www.reddit.com/r/Bitcoin/comments/2b8t78/whats_hodl/