Linear algebra extension tracking issue

[tomwhite]

This issue tracks the work needed to support the remaining linear algebra functions from the Python array API standard.

The current Cubed coverage status for the linalg extension can be found at https://github.com/cubed-dev/cubed/blob/main/api_status.md#linear-algebra-extension

• cholesky
• cross
• det
• diagonal
• eigh
• eigvalsh
• inv
• matrix_norm
• matrix_power
• matrix_rank
• pinv
• slogdet
• solve
• trace
• vector_norm

[tomwhite]

Here is a possible plan of attack. This is not in any particular order (since it would depend on what the demand is), but I've tried to tease out the dependencies between functions. Apart from some simpler array functions, most of the linalg functions depend on factorization functions like cholesky, lu, qr, or svd.

• simple functions (cross, diagonal, trace)
  • cross can be implemented using moveaxes, multiply (following NumPy)
  • diagonal has a fairly straightforward chunked algorithm (following Dask)
  • trace uses diagonal and sum
• factorization (cholesky, lu, qr, svd)
  • We have already implemented qr and svd in Cubed
  • lu and cholesky are closely related and can be computed for chunked arrays using "Blocked LU factorization" from https://homepages.math.uic.edu/%7Ejan/mcs572/parallelLU.pdf.
  • Note that lu is not (yet) standardised: RFC: add support for LU factorization in the linalg extension data-apis/array-api#627
• solving equations (inv, pinv, solve)
  • solve can be implemented using lu, cholesky, and solve_triangular (following Dask)
  • invcan be implemented using solve
  • pinv can be implemented usingsvd (see https://www.johndcook.com/blog/2018/05/05/svd/)
  • We might add solve_triangular and lstsq functions (not standardised, but in Dask)
• determinants (det, slogdet)
  • Use lu, see Add det/slogdet workaround for dask data-apis/array-api-compat#133 for a proposed Dask implementation
• eigenvalues (eigh, eigvalsh)
  • Use svd
• norms (matrix_norm, vector_norm)
  • Use simple reductions (sum, min), orsvd for singular value-based norms
• other (matrix_power, matrix_rank)
  • matrix_power can be implemented using repeated calls to matmul; or eye for n=0; or inv for n<0 (following NumPy)
  • matrix_rank can be implemented using svd

It would be interesting if there are more up-to-date chunked/blocked algorithms for any of these.