5 ms·

This does not seem to depend on BLAS/LAPACK. Good to see LU decomposition with full pivoting being implemented here (which is missing from BLAS/LAPACK). This g

This does not seem to depend on BLAS/LAPACK. Good to see LU decomposition with full pivoting being implemented here (which is missing from BLAS/LAPACK). This gives a fast, numerically stable way to compute the rank of a matrix (with a basis of the kernel and image spaces). Details: https://www.heinrichhartmann.com/posts/2021-03-08-rank-decomposition/ https://www.heinrichhartmann.com/posts/2021-03-08-rank-decom....

sarah-ek 2y ago
lapack does expose a full pivoting lu as far as i can tell? https://netlib.org/lapack/explore-html/d8/d4d/group__getc2_gab40de248b52eae8c638d72d951631795.html https://netlib.org/lapack/explore-html/d8/d4d/group__getc2_g...
- bee_rider 2y ago
  If you are going to include vs MKL benchmarks in your repo, full pivoting LU might be one to consider. I think most people are happy with partial pivoting, so I sorta suspect Intel hasn’t heavily tuned their implementation, might be room to beat up on the king of the hill, haha.
  - sarah-ek 2y ago
    funny you mention that, the full pivoting. it's one of the few benchmarks where faer wins by a huge margin n faer mkl openblas 1024 27.06 ms 186.33 ms 793.26 ms 1536 73.57 ms 605.71 ms 2.65 s 2048 280.74 ms 1.53 s 8.99 s 2560 867.15 ms 3.31 s 17.06 s 3072 1.87 s 6.13 s 55.21 s 3584 3.42 s 10.18 s 71.56 s 4096 6.11 s 15.70 s 168.88 s
    - adgjlsfhk1 2y ago
      it might be interesting to add butterfly lu https://arxiv.org/abs/1901.11371 https://arxiv.org/abs/1901.11371. it's a way of doing a numerically stable lu like factorization without any pivoting, which allows it to parallelize better.
      - sarah-ek 2y ago
        looks interesting! thanks for sharing
      - bee_rider 2y ago
        It looks like they are describing a preconditioner there.
        adgjlsfhk1 2y ago
        the key point is that the preconditioner allows you to skip pivoting which is really nice because the pivoting introduces a lot of data dependence.
- heinrichhartman 2y ago
  Thanks for pointing this out. Looks like only the python bindings are not included in nunpy.
bmitc 2y ago
Is there a collection of algorithms published somewhere, in a coherent manner? It seems like to me, there should be a collection of matrix algebra, symbolic algebra, etc. algorithms somewhere that makes it easy to implement these in any language or system. As it is, it seems you need to already be an expert or researcher in the space to make any movement.
- rvdca 2y ago
  One could argue that libraries like BLAS/LAPACK are those collections...
  - bmitc 2y ago
    That can be argued, but they're pretty esoteric. For example, what language are they written in? Fortran, assembly, etc.? Probably nothing the majority of developers or mathematicians can't understand. And creating bindings for them is non-trivial. I don't even know where to start from the website. And on the website, all the links to the routines are broken. https://www.netlib.org/blas/ https://www.netlib.org/blas/
    - 1980phipsi 2y ago
      The naming convention is a bit esoteric, but once you figure it out it's not too bad. I don't think writing bindings is too hard once you know what's going on. You most likely would want to write some kind of wrapper on top of that in order to make things a little more user-friend. I will agree with you on the routines being broken. That happened within the past year. Not sure why it happened, but it's annoying. If you know the name of the routine you can usually find documentation on another site.
- sevagh 2y ago
  BLIS is an interesting new direction in that regard: https://github.com/flame/blis https://github.com/flame/blis >The BLAS-like Library Instantiation Software (BLIS) framework is a new infrastructure for rapidly instantiating Basic Linear Algebra Subprograms (BLAS) functionality. Its fundamental innovation is that virtually all computation within level-2 (matrix-vector) and level-3 (matrix-matrix) BLAS operations can be expressed and optimized in terms of very simple kernels.
sevagh 2y ago
On the contrary, it seemingly can be used to make a BLAS implementation (example in a PR: https://github.com/sarah-ek/faer-rs/pull/37 https://github.com/sarah-ek/faer-rs/pull/37)

sarah-ek 2y ago

lapack does expose a full pivoting lu as far as i can tell? https://netlib.org/lapack/explore-html/d8/d4d/group__getc2_gab40de248b52eae8c638d72d951631795.html https://netlib.org/lapack/explore-html/d8/d4d/group__getc2_g...

bee_rider 2y ago
If you are going to include vs MKL benchmarks in your repo, full pivoting LU might be one to consider. I think most people are happy with partial pivoting, so I sorta suspect Intel hasn’t heavily tuned their implementation, might be room to beat up on the king of the hill, haha.
- sarah-ek 2y ago
  funny you mention that, the full pivoting. it's one of the few benchmarks where faer wins by a huge margin n faer mkl openblas 1024 27.06 ms 186.33 ms 793.26 ms 1536 73.57 ms 605.71 ms 2.65 s 2048 280.74 ms 1.53 s 8.99 s 2560 867.15 ms 3.31 s 17.06 s 3072 1.87 s 6.13 s 55.21 s 3584 3.42 s 10.18 s 71.56 s 4096 6.11 s 15.70 s 168.88 s
  - adgjlsfhk1 2y ago
    it might be interesting to add butterfly lu https://arxiv.org/abs/1901.11371 https://arxiv.org/abs/1901.11371. it's a way of doing a numerically stable lu like factorization without any pivoting, which allows it to parallelize better.
    - sarah-ek 2y ago
      looks interesting! thanks for sharing
    - bee_rider 2y ago
      It looks like they are describing a preconditioner there.
      - adgjlsfhk1 2y ago
        the key point is that the preconditioner allows you to skip pivoting which is really nice because the pivoting introduces a lot of data dependence.
heinrichhartman 2y ago
Thanks for pointing this out. Looks like only the python bindings are not included in nunpy.

bmitc 2y ago

Is there a collection of algorithms published somewhere, in a coherent manner? It seems like to me, there should be a collection of matrix algebra, symbolic algebra, etc. algorithms somewhere that makes it easy to implement these in any language or system. As it is, it seems you need to already be an expert or researcher in the space to make any movement.

rvdca 2y ago
One could argue that libraries like BLAS/LAPACK are those collections...
- bmitc 2y ago
  That can be argued, but they're pretty esoteric. For example, what language are they written in? Fortran, assembly, etc.? Probably nothing the majority of developers or mathematicians can't understand. And creating bindings for them is non-trivial. I don't even know where to start from the website. And on the website, all the links to the routines are broken. https://www.netlib.org/blas/ https://www.netlib.org/blas/
  - 1980phipsi 2y ago
    The naming convention is a bit esoteric, but once you figure it out it's not too bad. I don't think writing bindings is too hard once you know what's going on. You most likely would want to write some kind of wrapper on top of that in order to make things a little more user-friend. I will agree with you on the routines being broken. That happened within the past year. Not sure why it happened, but it's annoying. If you know the name of the routine you can usually find documentation on another site.
sevagh 2y ago
BLIS is an interesting new direction in that regard: https://github.com/flame/blis https://github.com/flame/blis >The BLAS-like Library Instantiation Software (BLIS) framework is a new infrastructure for rapidly instantiating Basic Linear Algebra Subprograms (BLAS) functionality. Its fundamental innovation is that virtually all computation within level-2 (matrix-vector) and level-3 (matrix-matrix) BLAS operations can be expressed and optimized in terms of very simple kernels.

sevagh 2y ago

On the contrary, it seemingly can be used to make a BLAS implementation (example in a PR: https://github.com/sarah-ek/faer-rs/pull/37 https://github.com/sarah-ek/faer-rs/pull/37)