---
title: "Multidimensional Array Indexing and Storage"
author: "Jan de Leeuw"
date: "Version 27, August 31, 2017"
output:
pdf_document:
keep_tex: yes
number_sections: yes
toc: yes
toc_depth: 3
html_document:
keep_md: yes
number_sections: yes
toc: yes
fontsize: 12pt
graphics: yes
bibliography: indexing.bib
abstract: We give R, C, and R->C code to access lineary stored multidimensional arrays and compactly stored multidimensional super-symmetric arrays.
---
---
```{r function_code, echo = FALSE}
source("indexing.R")
source("indexingC.R")
```
```{r packages, echo = FALSE}
options (digits = 10)
suppressPackageStartupMessages (library (captioner, quietly = TRUE))
figure_nums <- captioner (prefix = "Figure")
mprint <- function (x,
d = 6,
w = 8,
f = "") {
print (noquote (formatC (
x,
di = d,
wi = w,
fo = "f",
flag = f
)))
}
```
Note: This is a working paper which will be expanded/updated frequently. All suggestions for improvement are welcome. The directory [gifi.stat.ucla.edu/indexing](http://gifi.stat.ucla.edu/indexing) has a pdf version, the bib file, the complete Rmd file with the code chunks, and the R and C source code.
#Introduction
Suppose $A$ is an array of *rank* $r$ and *dimension* $(n_1,\cdots,n_r)$. Here rank is used in the APL sense, i.e. the length of the dimension vector.
$A$ has elements $a_{i_1\cdots i_m}$. It is easy enough to visualize, or at least conceptualize, these $n:=n_1\times\cdots n_m$ elements in an $m$-dimensional rectangular block of cells, but unfortunately such blocks cannot be stored directly in contiguous locations in computer memory. The array $A$ is usually stored in $n$ contiguous locations in memory, i.e. in a form that corresponds with a vector, an array of rank one.
Say $b$ is a pointer to the first element stored. We need a mapping $f$ from $\mathcal{I}_{n_1}\otimes\cdots\mathcal{I}_{n_m}$ into $\mathcal{I}_n$ such that $b+f(i_1,\cdots,i_m)$ is a pointer to $a_{i_1\cdots i_m}$. Or, using C, $b[f(i_1,\cdots,i_m)]=*(b+f(i_1,\cdots,i_m))$ must be equal to $a_{i_1\cdots i_m}$. Let's call such an $f$ an *index mapping*. We are interested in both the index mapping $f$ and its inverse
$f^{-1}:\mathcal{I}_n\rightarrow\mathcal{I}_{n_1}\otimes\cdots\mathcal{I}_{n_m}$.
If $A$ is symmetric, or anti-symmetric, or triangular, or hollow, then it is not necessary to store all its elements. This means that $f$ is no longer bijective, because fewer than $n$ elements are stored in memory. In fact, the main motivation for this paper is to derive the index mapping, and its inverse, for the super-symmetric arrays of partials derivatives discussed in @deleeuw_E_17r.
In this paper I review and program index mappings for arrays that can be used to assess and retrieve array elements from contiguous memory locations. I am $99.99\%$ sure there is nothing new in the paper, I just wanted to collect these results in a single convenient place, and provide code. As for the programming languages, we first develop in R, and then translate to C.
#Matrices
##General Rectangular Matrices
Storing the elements of a general rectangular matrix in contiguous locations in memory can be done in many ways, but two specific ones are the most obvious. We can store row one first, then continue with row two, and so on. This is *row major order*. Or we can store column one, append column two, and so on. That is *column major order*. If $A$ is
```{r echo = FALSE}
set.seed(12345)
mprint (a<-matrix(sample(1:12,12),4,3), w = 3, d = 0)
```
then column major order stores the matrix as
```{r echo = FALSE}
mprint(as.vector(a), w = 3, d = 0)
```
and row major order stores it as
```{r echo = FALSE}
mprint(as.vector(t(a)), w = 3, d = 0)
```
The index mapping for column major order is
```{r echo = FALSE}
k <- 1
for (j in 1:3) {
for (i in 1:4) {
cat(formatC(i, width = 2, digits = 2, format = "d"),
formatC(j, width = 2, digits = 2, format = "d"),
" *** ",
formatC(k, width = 2, digits = 2, format = "d"),"\n")
k <- k + 1
}
}
```
and for row major order it is
```{r echo = FALSE}
k <- 1
for (i in 1:4) {
for (j in 1:3) {
cat(formatC(i, width = 2, digits = 2, format = "d"),
formatC(j, width = 2, digits = 2, format = "d"),
" *** ",
formatC(k, width = 2, digits = 2, format = "d"),"\n")
k <- k + 1
}
}
```
Because the row index changes fastest, we could call column major ordering *first-fast*. Row major ordering has the second, i.e. the last index changing fastest, and could therefore be called *last-fast*. That terminology has the advantage it generalizes to multidimensional arrays, while the use of rows and columns is more or less limited to matrices.
The main application we have in mind is to pass matrices and arrays from R to C, with I/O and memory allocation done in R, and computation in C. This implies that the C versions of our indexing routines are the most useful ones.
R stores matrices first-fast (showing its origins, as a REPL interface to FORTRAN routines). Thus
then `a[3] = ``r a[3]` and `a[11] =``r a[11]`, because `as.vector(a)` is
```{r echo = FALSE}
as.vector(a)
```
First-fast is how the arrays arrive in C, where the index calculations are done to retrieve the elements. As a consequence, both for matrices and arrays, first-fast is the most relevant storage mode for our purposes.
We do not have to worry about how C stores matrices multidimensional arrays, because for our purposes it is better to pretend that C does not have any matrices or multidimensional arrays at all.
##Symmetric and Triangular Matrices
For symmetric and anti-symmetric matrices we only have to store half of the elements. This means making two choices,
first if we want to store the upper or the lower triangle, second if we want to use first-fast or last-fast. Storing the
lower triangle means storing all $a_{ij}$ with $i\geq j$, storing the upper triangle stores all $a_{ij}$ with $i\leq j$.
Because of generalization to multidimensional arrays we call the first option *decreasing* and the second option *increasing*.
We will choose the upper or increasing triangle combined with first-fast storage throughout. For a symmetric matrix we only have to store $N=\frac12 n(n+1)$ elements. The mapping function will be defined for all $i\leq j$, and it maps those index pairs bijectively on $1,\cdots,N$. This mapping function also has an inverse. We then extend the mapping function to all index pairs by first ordering the pair, making the extended mapping function surjective. We will not give the mapping function yet, because it will be just a special case of the one for super-symmetric arrays.
Just as an aside, our conventions imply that the elements of a lower triangular matrix, in which the non-zero $a_{ij}$ have $i\geq j$, will be stored in increasing or upper triangle form, in other words as its transpose.
The extended mapping function for that case, which we do not really consider in detail, will have to take that into account. Also, strictly lower and upper triangular matrices, anti-symmetric matrices, and symmetric hollow matrices such as distance matrices, only need to store $\frac12 n(n-1)$ elements. We do not discuss storage schemes that leave out the diagonal. We always store the diagonal elements, but the extended mapping function has no need to access them.
#Arrays
##General Arrays
Linear storage of the elements of a general array or rank $m$ and dimension $(n_1,\cdots,n_m)$ can be done in many ways. First-fast and last-fast are just two special cases of the $m!$ ways in which we can nest the index loops. Since going through all possibilities is both boring and unnessary we limit ourselves to first-fast. If, for whatever reason, another permutation of the indices is needed we can first transpose the array in R, for instance using `aperm()` from the base package, or `aplTranspose()` from @deleeuw_yajima_E_16.
The R version of the mapping function is `fArrayFirst()`.
Note that it is identical to the `aplDecode()` function from @deleeuw_yajima_E_16. For completeness we also give `fArrayFirstInverse()`, which is `aplEncode()`, the inverse $f^{-1}$, mapping $\mathcal{I}_n$ into $\mathcal{I}_{n_1}\otimes\cdots\mathcal{I}_{n_m}$.
Our example is a $4\times 3\times 2$ array. In tabular form the index mapping is
```{r, echo = FALSE}
n<-c(4,3,2)
a<-array(0,n)
for (k in 1:n[3]) {
for (j in 1:n[2]) {
for (i in 1:n[1]) {
l <- fArrayFirstRC(c(i,j,k), n)
cat(formatC(i, width = 2, digits = 2, format = "d"),
formatC(j, width = 2, digits = 2, format = "d"),
formatC(k, width = 2, digits = 2, format = "d"),
" *** ",
formatC(l, width = 2, digits = 2, format = "d"),"\n")
a[i,j,k] <- l
}
}
}
```
and in array form it is
```{r, echo = FALSE}
print (a, digits = 0, width = 3)
```
##Super-symmetry
An array $A$ of rank $m$ and dimension $(n,\cdots,n)$ is *super-symmetric* if $a_{i_1\cdots i_m}$ is invariant under permutation of indices. Think of arrays of product moments, cumulants, or partial derivatives. Super-symmetry generalizes symmetry of matrices.
In order not to drown in the $(m!)\times (m!)$ combinations of what-fast and
which-triangle, we limit ourselves to first-fast and increasing (i.e. index tuples with $i_1\leq\cdots\leq i_m$).
The number of elements we have to store is
$\binom{m+n-1}{m}$, instead of $n^m$. This can be a considerable saving of storage if $m$ and/or $n$ are at all large. For $n=10$
and $m=4$, for example, we save $93\%$ of the storage. For large $n$ the savings are approximately $100*(1-\frac{1}{m!})\%$.
The mapping function for a super-symmetric array, with first-fast and increasing index vectors, is
`fSupSymIncreasingFirst()`.
Note that this function does not need to know the dimensions of the array. Also it starts by sorting the elements of the index vector. Thus
```{r}
fSupSymIncreasingFirstRC(c(1,2,2,3))
```
and also
```{r}
fSupSymIncreasingFirstRC(c(2,1,3,2))
```
The inverse mapping is
`fSupSymIncreasingFirstInverse()`.
As an example, here is the result for a four-dimensional super-symmetric array of order four. There are only 35, instead of 256, elements to consider.
```{r, echo = FALSE}
allSupSymIncreasing <- function (dimension, rank) {
nm <- choose (dimension + rank - 1, rank)
for (k in 1:nm) {
i <- fSupSymIncreasingFirstInverseRC (dimension, rank, k)
cat(
formatC(
i,
width = 2,
digits = 2,
format = "d"
),
" *** ",
formatC(
fSupSymIncreasingFirstRC (i),
width = 2,
digits = 2,
format = "d"
),
"\n"
)
}
}
allSupSymIncreasing(4, 4)
```
#Implementation
There are four versions of the two basic functions `fArrayFirst()` for general arrays and `fSupSymIncreasingFirst()` for super-symmetric arrays. Two are in C, one which passes by value and returns integers, and a second one which wraps the first one, and passes by reference and returns void. And two are in R, one in pure R, and one which uses .C() to wrap a call to the compiled C code.
The two inverse functions `fArrayFirstInverse()` and `fSupSymIncreasingFirstInverse()` have only a single C version, which passes by reference and returns void. There are again two R versions of each, one in pure R and one a wrapper around a .C() call to the compiled C code.
#Appendix: Code
##R Code
###indexing.R
```{r file_auxilary, code = readLines("indexing.R")}
```
###indexingC.R
```{r file_auxilary, code = readLines("indexingC.R")}
```
##C Code
###indexing.h
```{c file_auxilary, code = readLines("indexing.h"), eval = FALSE}
```
###indexing.c
```{c file_auxilary, code = readLines("indexing.c"), eval = FALSE}
```
#References