Simple compact tree storage of a multidimensional array

Algorithms are described for storing and retrieving an array having a large and variable number of indices, each of which takes on values which are usually small integers, but whose maximum size is unknown. Such arrays are extremely common in physical problems, where the indices may be quantum numbers (describing the electrons in a many-electron atom, for example) or point separations on a lattice (as in the case of lattice Green functions). Usual methods for storing such arrays are very wasteful of space, and the resulting large memory requirements are often the limiting factor in the quality of physical calculations. The “trie” structure described here is conservative of memory. We have written a set of FORTRAN subroutines which allow a user to store and retrieve array elements efficiently without a detailed understanding of the tree structure; these are described in an accompanying write-up.