Proposal: Remove `upper` argument from `eigh` and `eigvalsh`

[lezcano]

Some functions that accept a symmetric matrix (eigh, eighvals) have an upper=False kwarg. According to the API:
“If True, use the upper-triangular part to compute the eigenvalues and eigenvectors. If False, use the lower-triangular part to compute the eigenvalues and eigenvectors.”.

There are a number of reasons why we might want to remove this argument from the API.

1. This kwarg goes against Point 4 of the design principles, as it biases the implementations towards “always assuming that the input is well-formed” (symmetric in this case) when it could very much not be the case. This prevents the implementations from throwing meaningful errors when the input is not symmetric.
2. Lack of orthogonality: The API does not offer a parameter of this kind for other functions that also accept a symmetric matrix as inputs such as cholesky. In fact, cholesky has a boolean parameter also named upper which does something completely different to eigh's upper.
3. Makes the semantics of autograd counterintuitive: This is not that relevant for this API as this API does not specify differentiation behaviour, but this API will potentially be followed by a number of frameworks that implement differentiation.
   It is not clear whether one should assume that the input is symmetric, or that the upper (resp. lower) triangular part of the input matrix input matrix represents a symmetric matrix via the transformation A.triu() + A.triu(1).T . This is problematic when computing the gradient, as it is not clear whether the gradient should be symmetric or upper triangular. PyTorch makes the gradient symmetric to be mathematically consistent with the semantics of the operation, rather than with the optimisation that this kwarg suggests, which is semantically wrong but more intuitive. We have not received any issue about this, which hints to the fact that almost no one uses this optimisation to pack two symmetric matrices into one unconstrained matrix (and an extra vector).
4. Lack of Orthogonality 2. It provides an optimisation that can be accomplished via the current API. If a user wants to pack two symmetric matrices with zero diagonal as the upper and lower-triangular part of a square matrix they could write L1, Q1 = linalg.eigh(A.triu(1) + A.triu(1).T); L2, Q2 = linalg.eigh(A.tril(-1) + A.tril(-1).T). Doing this and implementing symmetric gradients (which is what is mathematically correct for eigh) would give the correct semantics with respect to the upper (resp. lower) part of A.
5. Related to Point 3. eigh is defined in the API as “Returns the eigenvalues and eigenvectors of a symmetric matrix (or a stack of symmetric matrices) x.”, but this kwarg suggests that x should be a stack of upper (resp. lower) triangular matrices that encode symmetric matrices.

In summary, this is a feature that seemed to have made its way from LAPACK into numpy, and a number of other frameworks have implemented it for numpy compatibility. This was certainly the case of PyTorch. It could be of interest to deprecate it, as it is too low level for a generic API, and its behaviour can be implemented in a couple of lines, as described above.

cc @rgommers @mruberry

[kgryte]

Personally, I am okay with removing this keyword argument from the current specification. I agree that the upper keyword argument seems to make certain algorithmic assumptions (ala LAPACK), which we ostensibly want to avoid.

[kgryte]

One potential issue here is that the array API specification currently lacks APIs for returning the upper and lower triangular parts of an array. In which case, based on the specification alone, a user would be unable to pack two symmetric matrices (point 4 above).

We may want to consider adding those APIs.

[kgryte]

I've opened gh-237 to discuss adding tril and triu to the specification.

[leofang]

I have some concerns about removing upper. My understanding is eigh/eigvalsh do not require the input matrix to be symmetric/Hermitian because users can specify whether to use the upper or lower part through the upper argument, and internally the solver can always "reconstruct" a fully symmetric/Hermitian matrix accordingly if needed (ofc there are much smarter ways to proceed). As a result, users can actually pack two matrices compactly to save memory, and by setting upper properly we can compute the eigensystem potentially for two distinct matrices with the same input array (and they may share the same diagonal, don't have to be zero). Removing the upper keyword removes this convenience, and implicitly forces libraries to actually check if the input is symmetric or not by taking the docstring literally.

[lezcano]

@leofang The packing part is addressed in point 4.

[leofang]

@leofang The packing part is addressed in point 4.

No, that's not true, that's why I am concerned 🙂 Point 4 requires computing a temporary array A.triu(+-1) + A.triu(+-1).T, which increases memory footprint and compute overhead. It is not the same if you can literally pack two matrices in the same array A. Also, Point 4 requires the two matrices to have zero diagonal, which could have been be relaxed.

[lezcano]

This may not be the case if libraries implement LazyTensors.

That being said, there's also the point that, in PyTorch, we have been returning symmetric gradients for quite a few versions already, and we have not had any issue raised about this. This may indicate that not that many people use this feature.

[leofang]

It's good to know @lezcano! I look into it more and agree packing two matrices in the same array is more an application-specific optimization strategy, so it may not be widely adopted indeed.

[leofang]

OK, we discussed about the packing part. How about my other comment?

Removing the upper keyword ... implicitly forces libraries to actually check if the input is symmetric or not by taking the docstring literally.