feat: add `eig` and `eigvals` to the `linalg` extension

[ev-br]

Following up on an RFC at https://github.com/data-apis/array-api/issues/935, add non-symmetric eigenvalue solvers, eig and eigvals, to the linalg extension.

The routines are available in numpy, torch, jax.numpy and cupy (as of to-be-released cupy 1.14, cf https://github.com/cupy/cupy/pull/8980). The main point of contention in gh-935 was the behavior for all eigenvalues on the real line. NumPy returns a real array and all other libraries return a complex array (with zero imaginary parts if they happen to be zero). Based on the discussion in https://github.com/numpy/numpy/issues/29000, it might it be difficult to change in numpy itself. Therefore, the suggestion is to make the precise dtype implementation-defined. I believe the benefit of having eig in the standard outweighs this wart.

One other minor point of inconsistency is https://github.com/jax-ml/jax/issues/32558: jax returns a standard-compliant namedtuple for eigh but a bare tuple for eig. I believe this is a minor issue though. already fixed.

[kgryte]

Could we not handle the NumPy return type discrepancy in the compatibility layer? I.e., we'd standardize always returning a complex array and we'd smooth that over in the compat layer for NumPy?

[ev-br]

If push comes to shove, yes it's an option. I would argue to not go that route though. A minor technical reason is that numpy does extra work to return reals, and the compat layer would then do extra work on top to undo numpy's extra work.

A larger issue is what is the compat layer: is it a thin temporary layer to smooth over small incompatibilities for until array libraries match the standard, or is this something permanent where we correct the behavior of array libraries?

If we say it's OK to do an allocation for numpy's eig return, do we also correct the torch.sum behavior with unsigned ints? Do we provide shims for torch not accepting the scalars? Do we fix matmul dtypes? Do we provide missing dask.linalg functions? Do we smooth over cupy's not havaing device= arguments? These are just a few examples from the floodgate of https://github.com/data-apis/array-api-compat/issues?q=is%3Aissue%20state%3Aopen%20label%3A%22blocked%20by%20upstream%22

[ev-br]

As discussed in the Oct 16 consortium meeting, the preference is to require eigenvalues to be always of a complex dtype. The last commit updates the text accordingly, and fixes the dtype of eigenvectors (wihch is always complex, too).

[seberg]

the preference is to require eigenvalues to be always of a complex dtype.

Grumpy old man hat, but: If the NumPy issue isn't resoelved (and it possibly cannot, at least not for 2 years even if I agree), then I don't like this.

I am not opposed at all to just codifying this, but we should clarify the scope somewhere in this repo more clearly. As is someone will open an issue on the NumPy repo that NumPy "must follow the Array API" which is nonsense, because if NumPy cannot follow it then we can't put this in to begin with.

To me that is easy to resolve: Accept that exactly matching API in the main namespace is aspirational at best and actually document that clearly somewhere so I can point at it from the NumPy repo. Otherwise, I don't know what to do, because it seems to me I would have to veto adding this until the NumPy issue is resolved.

[rgommers]

I'm fine with accepting this PR as long as NumPy has made a decision to made the change (whether through flipping a switch in a future release, or through a deprecation process). That the standard and NumPy are temporarily misaligned is okay, and array-api-compat can be used by library authors to deal with that. A permanent mismatch isn't okay though, that would be a blocker for accepting this PR.