Many popular interconnection network topologies, such as hypercubes and toroidal meshes, are based on Cayley graphs of Abelian groups. The symmetry and algebraic structure of these graphs result in many nice physical properties of the network concerning layout, routing algorithms, and load balancing. There has been interest in low-diameter Abelian--Cayley graphs because of their smaller communication delay and reduced congestion. For any fixed number of nodes n, and any fixed out-degree k, we are interested in how small the diameter of directed Cayley graphs of Abelian groups can be and what these low-diameter graphs look like. We give an upper bound of $n \leq \frac{3(d + 3)^3}{25}$ for the size of directed Abelian--Cayley graphs with k = 3 and diameter d, correcting a previously published result by Hsu and Jia [SIAM J. Discrete Math., 7 (1994), pp. 57--71]. Our method is based on translational tiling techniques and is a generalization of Wong and Coppersmith's method for k = 2 [J. Assoc. Comput. Mach., 21 (1974), pp. 392--402]. Moreover, our method works for all Abelian groups, not just the cyclic case. For k = 3 we give computational results for the largest Abelian--Cayley graph as a function of diameter. When n = 84 m 3 , for integer m, there is a network with $n = \frac{(d + 3)^3}{11.95}$ whose diameter is approximately three-fourths of that of a three-dimensional toroidal cube.

The problem of choosing a static shortest-path system that minimizes maximum edge congestion in a network is studied. Bounds based on parameters, such as diameter, bisection width, and average distance, are derived and conditions for producing uniform congestion on all edges are explored. Trees are shown to have maximum congestion on edges that are incident to a centroid node. Cartesian product graphs, which generalize multidimensional meshes, are shown to satisfy several closure properties and a generic factor-routing scheme is defined and shown to be optimal in many cases.

The multistage shuffle-exchange network is generalized, by replacing the perfect shuffle with an arbitrary permutation π, in order to pass all permutations using aminimal number of stages. The universality of such a network is shown to be equivalent to theprimitivity of a related regular digraph, thus showing that universality is decidable in polynomial time. Extensive computational results are presented that characterizeall nonisomorphic minimal networks with up to 12 inputs. In addition, strong evidence is presented relating the minimal number of network stages needed to achieve universality totwice the index of primitivity of the corresponding digraph.

Pin minimization is an important issue for massively parallel architectures because the number of processing elements that can be placed on a chip, board, or chassis is often pin limited. A d-dimensional bused hypercube interconnection network is presented that allows nodes to simultaneously (in one clock tick) exchange data across any dimension using only d+1 ports per node rather than 2d. Despite this near two-to-one reduction, the network also allows nodes that are two dimensions apart to simultaneously exchange data; as a result, certain routings can be performed in nearly half the time. The network is shown to be a special case of a general construction in which any set of d permutations can be performed, in one clock tick, using only d+1 ports per node. A lower-bound technique is also presented and used to establish the optimality of the network, as well as that of several other new bused networks.>

The solutions to a scalar, homogeneous, constant-coefficient, linear recurrence are expressible in terms of the powers of a companion matrix. We show how to compute these powers efficiently via polynomial multiplication. The result is a simple expression for the solution, which does not involve the characteristic roots and which is valid for any module over any commutative ring. The formula yields the nth term of the solution to a kth order recurrence with $O(\mu (k) \cdot \log n)$ arithmetic operations, where $\mu (k)$ is the total number of arithmetic operations required to multiply two polynomials of degree $k - 1$. Thus if the ring supports a fast Fourier transform, then $O(k \cdot \log k \cdot \log n)$ operations are sufficient to compute the nth term.

An iterative mincut heuristic for partitioning networks is presented whose worst case computation time, per pass, grows linearly with the size of the network. In practice, only a very small number of passes are typically needed, leading to a fast approximation algorithm for mincut partitioning. To deal with cells of various sizes, the algorithm progresses by moving one cell at a time between the blocks of the partition while maintaining a desired balance based on the size of the blocks rather than the number of cells per block. Efficient data structures are used to avoid unnecessary searching for the best cell to move and to minimize unnecessary updating of cells affected by each move.

We present a new, “greedy”, channel-router that is quick, simple, and highly effective. It always succeeds, usually using no more than one track more than required by channel density. (It may be forced in rare cases to make a few connections “off the end” of the channel, in order to succeed.) It assumes that all pins and wiring lie on a common grid, and that vertical wires are on one layer, horizontal on another.

The foundations are laid for a theory of multiplicative complexity of algebras and it is shown how “multiplication problems” such as multiplication of matrices, polynomials, quaternions, etc., are instances of this theory. The usefulness of the theory is then demonstrated by utilizing algebraic ideas and results to derive complexity bounds. In particular linear upper and lower bounds for the complexity of certain types of algebras are established.

A polynomial p(x) can be evaluated at several points x1,...,xm by first constructing a polynomial d(x) which has x1,...,xm as roots, then dividing p(x) by d(x), and finally evaluating the remainder r(x) at x1,...,xm. This method is useful if the coefficient sequence of d(x) can be chosen to be sparse, thus simplifying the construction of r(x). The case m=1 and d(x) = x−x1 is Horner's rule, while the case d(x) = xm−1 yields the fast Fourier transform algorithm.

This paper deals with three aspects of algebraic complexity. The first section is concerned with lower bounds on the number of operations required to compute several functions. Several theorems are presented and their proofs sketched. The second section deals with relationships among the complexities of several sets of functions. In the third section, several matrices of general interest are examined and upper bounds on the number of operations required to multiply by them are constructively derived.