array-api icon indicating copy to clipboard operation
array-api copied to clipboard

RFC: add `kron` to compute the Kronecker product

Open lucascolley opened this issue 1 year ago • 0 comments

Prior art

  • NumPy - https://numpy.org/doc/stable/reference/generated/numpy.kron.html
  • CuPy - https://docs.cupy.dev/en/latest/reference/generated/cupy.kron.html
  • Dask - https://github.com/dask/dask/issues/3657
  • JAX - https://jax.readthedocs.io/en/latest/_autosummary/jax.numpy.kron.html
  • PyTorch - https://pytorch.org/docs/stable/generated/torch.kron.html
  • Tensorflow - https://github.com/tensorflow/tensorflow/blob/v2.16.1/tensorflow/python/ops/numpy_ops/np_math_ops.py#L436-L469

Motivation

We have an awkward function kron in scipy.linalg. We would like to deprecate the function and direct users to np.kron instead, like we have done for np.triu and np.tril. However, unlike those functions, xp.kron is not in the standard, hence we have been hesitant to deprecate in case it does not make it into the standard[^1]. Experiments done by @ilayn in https://github.com/scipy/scipy/issues/20077 demonstrate that there are big performance gains to be had with a native array library implementation. Also, an array-agnostic implementation by @mdhaber in https://github.com/scipy/scipy/issues/20077#issuecomment-2299980532 demonstrates that at least a Python-level solution is easily implementable in standard array libraries.

Whether kron can be included in the standard or not, it would be very useful for us to know either way, so that we can plan whether we should deprecate scipy.linalg.kron or not.

[^1]: this is a concern because scipy.linalg is a feasible home for an array-agnostic kron if it isn't in the standard - more info at https://github.com/scipy/scipy/issues/20077#issuecomment-1949281961

lucascolley avatar Aug 21 '24 15:08 lucascolley