Azara Blog: The "transpose" problem in computing

Blog home page | Blog archive

Google   Bookmark and Share
 

Date published: 2005/10/14

In computing one often comes across data structures which are effectively inhomogeneous order n tensors. A tensor is a multilinear "form". "Order n" means the form acts on a cartesian product of n vector spaces (so in a coordinate basis, the tensor has n indices). "Inhomogenous" means the n vector spaces are not necessarily the same.

The most common examples of tensors are vectors (n = 1) and (the basis-independent formulation of) matrices (n = 2). A vector V has components V_i where i ranges over some set (usually for numbers, i, where 0 <= i < D, for some D, the dimension). A matrix M has components M_ia, where i ranges over one set and (in general) a ranges over another.

Vectors are dead-simple to handle in computing, there is not much variation on the theme. Matrices are harder, because it is quite common that some times it is best to deal with M itself and other times it might be best to deal with the transpose of M, i.e. the matrix N with components N_ai = M_ia. (The transpose is sometimes called a pivot in certain contexts, e.g. in Excel.)

This might seem like not a big deal. But often there are algorithms where the D1 vectors x(i)_a = M_ia (if i ranges over a set of size D1) can be quickly manipulated, and that is how your data should be stored. If you also have another algorithm which relies on fast access to the D2 vectors q(a)_i = N_ai = M_ia (a ranges over a set of size D2) then you are in trouble. You want your data manipulated as both x(i) and as q(a). (Sometimes because you want to fix i or a.) The usual way to do this is just to take the transpose (or equivalent). But this is slow (and if you want to store both that means wasting memory, and then also having to keep both in sync).

As an example, suppose you have a molecule with A atoms. The coordinates of this molecule are effectively a matrix with dimensions A x 3 (unless you are a member of a religion such as theoretical physics where molecules live in 10 dimensions). If you believe in object-oriented programming you might define a structure Atom, which has attributes x, y and z. Then in memory your data would be A Atoms. Memory is linear and the he data would effectively be stored as (x_0, y_0, z_0, x_1, y_1, z_1, ..., x_(A-1), y_(A-1), z_(A-1)). (At least in C. In Python or Java or other fancy languages then forget it.) Alternatively you might believe that you would rather deal with three vectors, r, s and t, each of length A, where r = (x_0, x_1, ..., x_(A-1)) and similarly for s and t. Now the data would effectively be stored as (x_0, x_1, ..., x_(A-1), y_0, y_1, ..., y_(A-1), z_0, z_1, ..., z(A-1)). Which form is better? Well it depends what you are calculating. If you want to rotate the molecule the first form is preferable, if you want to calculate the centroid the second form might be preferable.

As another example, a relational database table is effectively a matrix, where one index loops over the rows and the second index loops over the columns. Sometimes you might need a specific row (SELECT * from table where key=some_value). Sometimes you might need a specific column (SELECT column from table). Needless to say, a row of a matrix, M, is the same as a column of the transpose matrix, N.

The situation even gets worse for higher n. With an order-3 tensor there are six permutations for the index order (*_iaf, *_ifa, *_aif, *_afi, *_fai, *_fia). And so on. (With these higher order tensors you often end up projecting down to smaller order ones.) (Relational databases are poor at handling this kind of data.)

For example, in a business model for telephone calls you might want to consider revenue as a function of customer type, time of day and destination. This leads to an order-3 tensor R_iaf, where, for example, i = customer type = (residential, small business, large business), a = time of day = (weekday day, weekday night, weekend), and f = destination = (local, national, international, mobile). Sometimes you might want to fix customer type, sometimes time of day and sometimes destination.

No matter what way you choose to represent or store data for these kinds of problems, for certain calculations it will turn out to be the "wrong" way.

_________________________________________________________
All material not included from other sources is copyright cambridge2000.com. For further information or questions email: info [at] cambridge2000 [dot] com (replace "[at]" with "@" and "[dot]" with ".").