The Overlay class: Grow an abstraction layer for a range of Matrices

[ChristophWWagner]

Currently, we feature many matrix types that allow certain basic modifications of already defined matrix instances of limited scope. Among these are:

• Blocks
• BlockDiag
• Sum
• Permutation
• Zero
• Eye

This issue proposes a new matrix type, referred to as Overlay, which will be a superset of the listed matrices' functionality. In the following sections I will introduce the motivation behind this idea and outline some aspects of implementation.

Scope of this proposal as a list

• Introduce the overlay matrix baseclass that implements the behaviour described in the following sections
• Derive Blocks, BlockDiag, Sum, Permutation from Overlay, effectively only specifying __init__ and the required tests.
• Derive LFSRCirculant from Overlay in similar fashion as it can be fully expressed by Overlay by utilizing its Permutation capability

Basic Idea and structure

• The Overlay matrix is basically a Blocks on steroids, adding the essence of Sum and Permutation
• Organize the processing flow around individual child matrix instances involved instead of their location. This way reducing the amount of actuall forward/backward calls is greatly reduced if one or many particular instances occur multiple times across the structure.
• An Overlay instance is fully defined by a dictionary containing key:value pairs of type Matrix instance: list of mapping for all individual matrix instances that occur (that are nested) in a Overlay instance. Each occurance of an instance is represented either by a mapping datastructure that describes how the rows and columns of that instance get mapped into the image space of the to-be-defined Overlay instance, or by None in which case the transformation specified by the instance is not altered. The list therefore contains one mapping definition (be it of type mapping or None) for each occurance of the particular nested matrix instance, describing how it maps into the mapping space of the Overlay-instance-under-construction.
• This mapping based on the rows and columns of a particular matrix then allows to:
  • subselect or reorder a set of rows/cols of the particular instances' occurance (full indexing by means of a ndarray, resembling the functionality of Partial, which by itself is a superset of Permutation)
  • arrange this modified transform in a uniform subset of rows and columns in the targeted Overlay instance (limited, gridded subselection in the style of a slice that allows to greatly reduce the amount of indexing memory required for larger Overlay instances)
• The shape of an Overlay matrix instance will be extracted by the mappingdefinitions in the parameter dictionary. (simply determined by the highest index addressed) or it can be defined explicitly upon initialization. If defined upon initialization the parameter dictionary will be checked for indexing violations within that structure to relief the hassle of debugging that fecal-matter-bombarded-fan-of-matrix-definition-structure a little bit.
• Unaddressed elements in a Overlay matrix instance are assumed to default to zero
• Instantiating an Overlay instance based on an empty parameter dictionary requires the specification of the desired matrix shape, ultimatively leading to the definition of a Zero matrix this way
• Instantiating an Overlay instance with a set of multiple instances of exactly one occurance each and no further defined mapping is equivalent to the functionality of the Sum class

Example case

Consider a BlockDiagonal matrix where all blocks are equal
In this case the overlay matrix instance is defined by a dictionary contains exacly one pair matrix instance:list of mapping that maps the matrix to-be-repeated-along-main-diagonal matrix instance to the locations it shall appear in the to-be-defined matrix.
NOTE: The locations not neccessarily need to share a common block grid and each individual occurance may be transformed (permutated, partialed) as required.

Other effects and new matrix types

• Self-inference of Overlay types is now possible that allows automatic flattening of a matriix definition hierarchy over an arbitrary amount of levels, leading to self-optimization of anything that involves nesting one of the listed matrix types above
• A new Pad transform that allows Zero-Padding a matrix along rows and/or columns in a straightforward way
• The definition of sparse block structures is much easier this may
• Multiple occurances of one particular matrix instance in an Overlay instance can now be exploited by invoking only one transform of instance for all occurances (replicated as extra columns to the transform of instance) at the same time. This can drastically reduce call overhead for matrices with many occurances of otherwise identical matrices

Further suggestions

• By consequent application of core.stride offerings the generation of ndarray views for indexing purposes could be avoided in most cases, effectively leading to further performance enhancements over the baselin Blocks implementation.

Thank you for the following discussion!