Flattened Arrays and Multi-Indices
© 17 Jan 2013 Luther Tychonievich
Licensed under Creative Commons: CC BY-NC-ND 3.0
other posts

algorithm

A problem I keep encountering and its solution.

 

Vectors are lists of numbers. Matrices are squares of numbers. These two show up in many applications, and many computational libraries exist for solving them.

But what tensors: cubes and hypercubes of numbers? It seems as though I am continually re-encountering these. Multi-dimensional polynomials, accelerations in multidimensional time, data collected from planar laser-induced florescence—it’s not like these are every-day kinds of tasks; they just are tasks that my research runs into. And since they are not common, there aren’t many libraries for them out there.

Multi-Index Operations

Suppose you have a m-dimensional tensor. You can express it’s size with a list of m sizes: N = [n1, n2, …, nm]. A multi-index is a list of indices, one for every dimension of a tensor: I = [i1, i2, …, im]. Per computing tradition (and because it makes moduli more convenient) I assume that 0 ≤ ij < nj. I could have done 1 ≤ ij ≤ nj instead but that makes the math more complicated. Each multi-index names one cell in the tensor, and each cell in the tensor has exactly one multi-index referring to it.

The most basic operation of a multi-index in a computer is to treat a big vector or array as if it were a tensor. For this, as well as many operations that follow, it is useful to define the product of earlier sizes, pj ≜ ∏jk=1 nk. With this, converting a multi-index into a flat index is as simple as ∑mk=1 ik pk–1.

Two more operations make multi-indices useful tools in practice: partial enumeration and subindex replacement. I’ve never seen these discussed elsewhere, so the name, notation, etc., are original; if someone knows other names for them I welcome feedback in the comments.

Subindex replacement is very simple. Given a multi-index I = [i1, i2, … im], the subindex replacement Ik=x = [i1, …, ik–1, x, ik+1, … im].

Partial enumeration lists all valid multi-indices with a particular subset of the sub-indices fixed at 0. The simplest implementation I know is via partial increments:

Partial enumeration
for each fixed index j { temporarily set nj to 1 }; let I = [0, 0, …, 0]; repeatedly { for each j from 1 to m { let x = ij + 1; if xnj { update I to be Ij=0 } otherwise { update I = Ij=x; emit I; exit this “‍for each‍” loop } }; if I = [0, 0, …, 0], stop enumerating }

It is possible to efficiently implement multi-indices using only a single integer instead of a list of integers, but that is a subject too technical for this post.

Why this post?

Usually I make posts because I think some one of my usual readers will be interested. This post is unusual in that I don’t expect any of the readership I know about to find anything within it of value. As I said, tensors aren’t really all that common. But I didn’t find this information when I searched for it and thought it might be nice to share it in case someone is searching for it.




Looking for comments…



Loading user comment form…