The multiplicative complexity of discrete cosine transforms (DCTs) of arbitrary dimensions on input sizes, which are powers of two, are obtained. New upper bounds on the multiplicative complexity of scaled DCTs on input sizes, which are powers of two, are also obtained.>

We present a new method for accelerating matrix multiplication asymptotically. This work builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.

A problem related to the decentralized control of a multiple access channel is considered: Suppose k stations from an ensemble of n simultaneously transmit to a multiple access channel that provides the feedback 0, 1, or 2+, denoting k = 0, k = 1, or k ≥ 2, respectively. If k = 1, then the transmission succeeds. But if k ≥ 2, as a result of the conflict, none of the transmissions succeed. An algorithm to resolve a conflict determines how to schedule retransmissions so that each of the conflicting stations eventually transmits singly to the channel. In this paper, a general model of deterministic algorithms to resolve conflicts is introduced, and it is established that, for all k and n (2 ≤ k ≤ n ), Ω( k (log n )/(log k )) time must elapse in the worst case before all k transmissions succeed.

The main results of this paper have the following flavor: Given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that $\omega $, the exponent for matrix multiplication, is a limit point, that is, it cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that $\omega < 2.495548$.

The main results of this paper have the following flavor: given one algorithm for multiplying matrices, there exists another, better, algorithm. A consequence of these results is that ω, the exponent for matrix multiplication, is a limit point, that is, cannot be realized by any single algorithm. We also use these results to construct a new algorithm which shows that ω ≪ 2.495364.

Abstract We prove the direct sum conjecture for various sets of systems of bilinear forms. Our results depend on a priori knowledge of the complexity of at least one of the direct summands and its underlying algebraic structure. We also briefly survey some previous results concerning the complexity and structure of minimal algorithms for various direct sum systems.

In processing long sequences of data either for the purpose of filtering or spectal analysis, one generally divides the data into segments. The elements of each segment are usually multiplied by a set of weights, referred to as a "window", to reduce certain undesired effects of the division into short sequences (see Ref. 1). A simple effective way to design a window is to use one of the many window functions such as the Hanning, Hamming (1) or Kaiser (2) windows. These are defined by simple formulas in which parameters can be selected so that the frequency response of the window will have the desired center-lobe width and side-lobe attenuation. These procedures have the advantage that they require no more than a pocket calculator. On the other hand, if one is equipped with a large computer with filter design programs such as those in the IEEE Program Book (3), one may find it easier, in some cases, to design better windows by the direct calculation of an optimized filter. The present work shows the results of computations of FIR filters and how they compare with Hanning, Hamming and Kaiser windows. We get, for typical filter parameters, a side-lobe attenuation of 31.5 dB for the Hanning window, 42.0 dB for the Hamming window, 41.0 dB for the Kaiser window and 47.2 dB for the FIR window.

Some recent work (1) has shown how one can compute limited portions of the discrete Fourier transform (DFT) of a long sequence by first passing it through a decimating FIR filter and then using the FFT algorithm on the result. The filter is designed by an easily available program (2) to put a pass-band at the desired frequencies and stop-bands at all frequencies which will be aliased into the pass-band by the decimation. It is shown here how one may relax the constraints put upon the pass-band of the filter and significantly shorten the filter impulse response with a corresponding reduction in the amount of computation. A second innovation is to show how a set of cascaded decimating filters may be designed which requires less arithmetic and storage than a single large decimating filter. This reduction is achieved by designing each cascaded filter so as to take into account the attenuation of the preceding filters.

The multiplicative complexity of the direct product of algebras $A_p $ of polynomials modulo a polynomial P is studied. In particular, we show that if P and Q are irreducible polynomials then the multiplicative complexity of $A_{\text{P}} \times A_{\text{Q}} $ is $2\deg ({\text{P}})\deg ({\text{Q}}) - {\text{k}}$, where k is the number of factors of P in the field extended by a root of ${\text{Q}}$.

We present an approach to perform the conversion between two widely used multiplexing techniques in telephony, time division, multiplex (TDM) to frequency division multiplex (FDM), using digital signal processing techniques. By exploiting some results from the theory of computational complexity we reduce considerably the number of computations required. Furthermore the use of only nonrecursive (FIR) filters whose coefficients are expressed in the canonical signed digit code permits a 16 bit implementation requiring no multiplications and only additions with concurrent shifts which further simplifies the required circuitry.

A correspondence between linear(n,k,d)codes and algorithms for computing a system\psiofkbilinear forms is established under which the codelengthnis equal to the multiplicative complexity of the algorithm for computing\psi, and the code distancedis underbounded by the minimum number of multiplications required to compute any linear combination of thekforms in\psi. This hitherto unexplored approach to linear codes holds promise of a better understanding of the structure of existing codes as well as for methods of constructing new codes with prescribed rate and distance.

The time required to evaluate arithmetic expressions using parallel processing is investigated It is shown that for the evaluation of an arithmetic expression of n variables without division, in which every variable appears only once, at most 3n/2p ~ o(n) time umts are required if p processors are used In case the expression includes the division operation, the bound is raised to 5n/2p -~-o(n).

Abstract—In this note we describe a new way of computing the inner product of two vectors. This method cuts down the number of multiplications required when we want to perform a large number of inner products on a smaller set of vectors. In particular, we obtain that the product of two n×n matrices can be performed using roughly n3/2 multiplications instead of the n3multiplications which the regular method necessitates.

A set equations in the quantities a i ( p ), where i = 1, 2, · · ·, m and p ranges over a set R of lattice points in n -space, is called a system of uniform recurrence equations if the following property holds: If p and q are in R and w is an integer n -vector, then a i ( p ) depends directly on a j ( p - w ) if and only if a i ( q ) depends directly on a j ( q - w ). Finite-difference approximations to systems of partial differential equations typically lead to such recurrence equations. The structure of such a system is specified by a dependence graph G having m vertices, in which the directed edges are labeled with integer n -vectors. For certain choices of the set R , necessary and sufficient conditions on G are given for the existence of a schedule to compute all the quantities a i ( p ) explicitly from their defining equations. Properties of such schedules, such as the degree to which computation can proceed “in parallel,” are characterized. These characterizations depend on a certain iterative decomposition of a dependence graph into subgraphs. Analogous results concerning implicit schedules are also given.

The time required to perform multiplication is investigated. A lower bound on the time required to perform multiplication, as well as multiplication modulo N , is derived and it is shown that these lower bounds can be approached. Then a lower bound on the amount of time required to perform the most significant part of multiplication (⌞ xy / N ⌟) is derived.

A procedure for index register allocation is described. The rules of this procedure are shown to yield an optimal allocation for “straight line” programs.

In this paper we study some relations between the continuity of sequence transformations and their realizability by logic nets. The main results discussed include: the Curtis-Hedlund-Lyndon theorem which states that, if a sequence transformation is continuous and unitary (commutative with the shift transformation), then it can be realized by a net without feedback, and, the extension of this theorem to the finitary case. We find that unitary transformations are realized by definite automata, and finitary transformations are realized by indefinite automata. The term ``automata'' is used here in a modification of its usual sense, and we explore the relation between the conventional and modified notions. Many of the concepts and more significant mathematical results in this report can be found in another context in works by Hedlund and others. What may be new and of interest to computer scientists, we believe, is their application to the theory of sequential circuits.

4bslracl.The time required to perform a group operation using logical circuitry is investigated.A lower bound on this time is derived, and in the ease that the group is abelian it is shown that the lower bound can be approached as the complexity of the elements used i~ereases.In particular, if the group operation is adding integers modulo t~, it, is shown that the lower bound behaves as log log a(t~), where a(,) is the largest power of a prime which divides ~.

Some properties of automata are investigated, which are capable of limiting the effect of input errors on their behavior.First necessary and sufficient conditions arc derived for an automaton to be capable of always being resynchronized within a bo~mded xmmber of input letters after an error has occurred, and then the results are specialized to finit e-state completely specified automata.Automata are investigated, which are capable of being resynchronized with probability one and it is shown that a finite-state completely specified automaton possesses this property if and only if there exists a finite sequence which is a universal synchronizer for the automaton.Some connections with similar problems for vari~bleAength codes are indicated.

In recent years adaptive threshold ele-ments have been used as the basis for learning machines such as the Perceptron [1] and Adaline [2]. To the author's knowledge there has been no previously reported work on a systematic study of algorithms, used in learning machines, to modify the weightvalues of threshold elements.