Flattened Arrays and Multi-Indices

algorithm# Multi-Index Operations

Partial enumeration
# Why this post?

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.

Suppose you have a `m`-dimensional tensor.
You can express it’s size with a list of `m` sizes:
`N` = [`n _{1}`,

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,
`p`_{j} ≜ ∏^{j}_{k=1} `n`_{k}.
With this, converting a multi-index into a flat index
is as simple as
∑^{m}_{k=1} `i`_{k} `p`_{k–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` = [`i _{1}`,

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:

for each fixed index `j` { temporarily set `n`_{j} to 1 };
let `I` = [0, 0, …, 0];
repeatedly {
for each `j` from 1 to `m` {
let `x` = `i`_{j} + 1;
if `x` ≥ `n`_{j} {
update `I` to be `I`_{j=0}
} otherwise {
update `I` = `I`_{j=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.

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.

Loading user comment form…

Looking for comments…