Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] acmt_v1_0.gz(5 Kbytes)
Manuscript Title: User-friendly routines for tree storage and retrieval of multidimensional arrays.
Authors: P.B. Visscher
Program title: TESTSUB
Catalogue identifier: ACMT_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 31(1984)319
Programming language: Fortran.
Computer: UNIVAC 1100/60.
Operating system: UNIVAC EXEC LEVEL 37.
RAM: 1K words
Word size: 36
Keywords: General purpose, Utility, Multidimensional arrays, Tree structures, Sparse arrays.
Classification: 4.14.

Nature of problem:
Many physical problems require the use of large multidimensional arrays such as Z(I1,...IL), in which the indices IJ are small integers: quantumnumbers of orbitals in atomic physics, lattice-point separation vectors in solid-state physics, etc. If the arrays are very far from rectangular, tree storage is by far the most efficient (and often the only practical) storage technique. However, most physicists are not familiar with tree-storage algorithms, and are therefore forced to do the problem very inefficiently or not at all. The subroutine package presented here is designed for a user who knows nothing about tree structures. It allows him to store and retrieve array elements from a tree structure while thinking of it as a simple rectangular Fortran array.

Solution method:
The user supplies a list of L-tuples Il,...IL with the corresponding values for Z(Il,...IL). Subroutine INTREE puts these L-tupes into a simple tree structure. The list can then be reproduced sequentially by subroutine FIRST, or randomly accessed by subroutine IAD.

Running time:
In most applications the time spent in these subroutines is a negligible fraction of the total. The time required to retrieve one array element is roughly proportional to the sum of its indices.