Repository: pytorch
Issue: Upper/Lower attributes for named dimensions for proper Ricci notation and to generalize matrix operations
Labels: triaged,module: named tensor

## 🚀 Feature
1. Add an "upper|lower|unspecified" attribute to each (named) tensor dimension.
2. Honor the upper/lower distinction when checking dimension equality (upper!=lower, upper==unspecified, lower==unspecified, and of course lower==lower, upper==upper) in operations such as add, mul
3. Provide a method to match pairs of upper and lower dimensions which share the same name
4. Make all operators and algorithms specified on matrices available to all tensors with more than one upper and lower dimension (transpose, inverses, decompositions,...)

## Motivation

In multilinear/tensor algebra, there is a clear distinction between upper and lower indices, which (among other things) can be understood to distinguish between input and output dimensions.
By having a distinction between inputs and outputs, we can generalize any operations on linear maps (i.e. matrices) to tensors of arbitrary dimensionality, e.g. we can apply the matrix transpose, matrix inverses, matrix decompositions, and in general any algorithm defined on matrices in a mathematically consistent way:

**Flatten:** 
Reshapes any tensor into a _matrix_ with row index = cartesian product of all upper indices and column index = cartesian product of all lower indices.

Note that with this definition of flattening, we can generalize any matrix operation to any tensor, e.g. transposes, inverses, decompositions,... by applying it to the flattened tensor and reshaping (folding) it afterwards.

Note 2: The current flat() method basically assumes that all dimension have the same attribute value

**Transpose:** 
Flip the upper/lower attribute (upper to lower and lower to upper)

Note: this is the equivalent of swapping row and column in a matrix. 

Note: Currently, transpose() reverses the order of dimensions in the underlying data array by default. Dimension order should be an irrelevant implementation detail in a named tensor scheme, though (and maybe left to a compiler for optimization). For future compatibility, reordering could be restricted to tensors with at least one "unspecified" dimension.

**Inverses:**
 Invert the flattened tensor, then fold it back into its original shape. Upper/lower attributes get flipped.
 
Note: It may make sense to implicitly transmogrify some index names of the resulting output tensor, so that contracting the tensor with its inverse yields another tensor (instead of a scalar). for example, the lower indices of a left-sided pseudoinverse would match upper indices of its operand, but upper indices would not match the lower indices of the operand. This asymmetric name change effectively encodes the "left-sidedness" of the inverse, as tensor contraction (in contrast to matrix multiplication) is commutative. 

**contraction/tensordot:** 
Tensordot sums over pairs of indices with the same name but differing upper/lower attribute. For backwards compatibility, tensordot matches names with "unspecified" attribute with any other name.

(Here, no additional functionality is gained over named indices, but it makes tensordot a proper implementation of the tensor contraction as defined in the Ricci-notation)

**Coordinate transformation / Change of basis**
Coordinate transformation of tensors can be done automatically, as the upper/lower attribute distinguishes contravariant from covariant indices, i.e. it completely specifies how the coordinate values of a tensor need to be transformed under a change of basis. This is an inherent feature of proper tensors and extensively used in Physics and Mechanics,


A complementary purpose of the upper/lower attribute is to explicitly distinguish between maps (inputs and outputs), metrics(only inputs), and multidimensional data (only outputs). Invalid operand combinations (in the Ricci notation and multilinear algebra sense) could raise exceptions.

Unfortunately, we cannot simply use some naming scheme to handle the upper/lower distinction, as the semantics with respect to matching dimensions for tensor contraction differ (names use *equality* while upper/lower uses *inequality*).

## Pitch

Currently, no popular "tensor" library implements tensors such that they are fully compatible with the Ricci-notation, which is the most common notation to specify tensor equations. Pytorch already is well positioned though by the recent addition of named dimensions. Adding (optional) upper/lower attributes to each dimension would allow Pytorch users to implement tensor equations verbatim, improving code readability and avoiding bugs when implementing textbook equations.

From a practical, software engineering perspective, the upper/lower attribute provides an additional check when constructing elaborate computation graphs by distinguishing whether a dimension is supposed to consume data (input dimension, or lower index), or is supposed to provide data (output dimension, or upper index). 

For tensors with two dimensions, "upper" and "lower" is equivalent to the row-and-column distinction in matrix notation, so it is a straightforward and robust generalization.

In the far future, the change may also enable Pytorch to natively support algorithms from multilinear algebra, e.g. tensor decomposition algorithms. 


## Alternatives

The alternative is to comment-code the input-output direction semantics, similar to how dimension semantics had to be handled before introducing named dimensions. This is obviously error-prone and bad from a code-as-documention perspective. 


cc @zou3519