This is the multiple and multivariate extension of the one-dimensional case treated recently by the same author [Numer. Math. 68, No. 4, 507-547 (1994; Zbl 0808.65145)]. The present algorithms share the properties of the one-dimensional case: they are practically in-place, data access is mainly in stride 1 and they are well suited for vector-parallel implementation. As in the one- dimensional case this performance is obtained by mixed radix number representation, corresponding to writing the transform matrix as a Kronecker product of matrices. A performance indicator (for loop overhead) is developed further in this paper. Optimization of this index suggests rearrangements of the data in the case of multiple transforms. Numerical experiments achieve a typical speedup between 2 and 5. Similar algorithms for a multivariate transform are suggested. In principle these are independent of the one-dimensional implementation. Also here a similar speedup can be obtained, but not always.