We present a description and initial results of a computer code that coevolves fuzzy logic rules to play a two-sided zero-sum competitive game. It is based on the TEMPO military planning game that has been used to teach resource allocation to over 20,000 students over the past 40 years. No feasible algorithm for optimal play is known. The coevolved rules, when pitted against human players, usually win the first few competitions. For reasons not yet understood, the evolved rules (found in a symmetrical competition) place little value on information concerning the play of the opponent but rather focus on exploiting the available weapon systems.

This paper presents a design methodology for developing efficient distributed-memory parallel programs for block recursive algorithms such as the fast Fourier transform (FFT) and bitonic sort. This design methodology is specifically suited for most modern supercomputers having a distributed-memory architecture with a circuit-switched or wormhole routed mesh or a hypercube interconnection network. A mathematical framework based on the tensor product and other matrix operations is used for representing algorithms. Communication-efficient implementations with effectively overlapped computation and communication are achieved by manipulating the mathematical representation using the tensor product algebra. Performance results for FFT programs on the Intel Paragon are presented. © 1998 John Wiley & Sons, Ltd.

This paper presents a design methodology for developing efficient distributed-memory parallel programs for block-recursive algorithms such as the fast Fourier transform and bitonic sort. This design methodology is specifically suited for most modern supercomputers having a distributed-memory architecture with circuit-switched or wormhole routed mesh or hypercube interconnection network. A mathematical framework based on the tenser product and other matrix operations is used for representing algorithms. Communication-efficient implementations with effectively overlapped computation and communication are achieved by manipulating the mathematical representation using the tenser algebra. Performance results for FFT programs on the Intel iPSC/860 and Intel Paragon are presented.

We address the development of efficient methods for performing data redistribution of arrays on distributed-memory machines. Data redistribution is important for the distributed-memory implementation of data parallel languages such as High Performance Fortran. An algebraic representation of regular data distributions is used to develop an analytical model for evaluating the communication cost of data redistribution. Using this algebraic representation and the analytical model, an approach to communication-efficient data redistribution is developed. Implementation results on the Intel iPSC/860 are reported.

Presents EXTENT (EXpert system for TENsor product formula Translation) which is a programming environment for the automatic generation of parallel/vector programs from tensor product formulas. A tensor (Kronecker) product based programming methodology is used for designing high-performance programs on various architectures. In this programming methodology, block recursive algorithms such as the fast Fourier transform and Strassen's matrix multiplication algorithm are expressed as tensor product formulas involving tensor product and other matrix operations. A tensor product formula can be systematically translated into parallel and/or vector code for various parallel architectures. A prototype system which generates programs for the Cray Y-MP, Cray T3D and Intel Paragon has been developed. Performance results for some generated programs are presented.>

We p~esent transposition a~gorithms fo?' matrices that do not fit in main memory.Transposition is interpreted m a permutation of the vector obtained by mapping a matriz to linear memoTy.A lgopithms am derived j%om factorization of this perm~tation, using a class of permutations related to the tensor prodwt.Using this formulation of transposition, we jirst obtain seveTal known aigo?'ithms and then we derive a new algorithm which Teduces the number of dish accesses TequiTed.The new algoTithm was compaTed to ezisting algorithms wing an implementation on the Intel iPSC/860.Thti comparison shows the benefits of the new aigoTithm.

The authors present an algebraic theory based on tensor products for modeling direct interconnection networks. This theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. This theory can be used for mapping algorithms expressed in tensor product form onto distributed-memory architectures. The authors focus on the modeling of direct interconnection networks. Rings, n-dimensional meshes, and hypercubes are represented in tensor product form. Algorithm mapping using tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks.>

The authors study the use of multilinear algebra in designing and implementing algorithms for linear computations. In particular, they discuss their experience in using these techniques on the Cray Y-MP and to implement Strassen's matrix multiplication algorithm on the Encore Multimax. It is concluded that the formulation of numerical algorithms in terms of the constructs of multilinear algebra, especially the tensor product, together with the coding methods presented, simplifies the writing of the programs for implementing these algorithms. By making the implementation process simpler and more mechanical, one can more easily experiment with and monitor the coding of these algorithms and thereby find better implementations.>

New noncommutative bilinear algorithms for $3 \times 3$ matrix multiplication are presented. These have the same complexity, 23 essential multiplications, as the one discovered by Laderman, but are inequivalent to it. Equivalence here refers to a certain group of transformations all of which map noncommutative bilinear matrix-multiplication algorithms into other such algorithms; “inequivalent” means not related by a transformation in the group. This group has been studied by de Groote, who has shown for the case of $2 \times 2$ matrix multiplication with 7 essential multiplications that all such algorithms are equivalent to Strassen’s. The new algorithms, by contrast, include infinitely many pairwise inequivalent algorithms. The computer search that led to the new algorithms is described.

A new method is presented for estimating the power spectral density matrix for multichannel data, given correlation values for linear combinations of the channels and given an initial estimate of the spectral density matrix. A derivation of the method from the relative-entropy principle is given. The results differ significantly from the Multisignal Relative-Entropy ("Minimum-Cross-Entropy") Spectrum Analysis of Johnson and Shore because the present method does not arbitrarily force the final distributions of the various channels to be independent. For the special case when correlation values are given only for the sum of the channels, Multichannel Relative-Entropy Spectrum Analysis is shown to reduce to a two-stage procedure: first a smooth power-spectrum model is fitted to the correlations of the sum; then final estimates of the spectra and cross spectra are obtained through linear filtering. Illustrative numerical examples are presented.

This paper presents a new multisignal spectrum-analysis method based on the relative-entropy principle ("principle of minimum cross entropy"). The method simultaneously estimates a number of power spectra given (1) an initial ("prior") estimate of each, (2) imprecise values of the autocorrelation function of their sum, and (3) estimates of the error in measurement of the autocorrelation values. One application is to the separate estimation of the spectra of a signal and independent additive noise, based on imprecise measurements of the autocorrelations of the signal plus noise. A derivation is sketched, beginning with a discussion of relative-entropy minimization subject to quadratic constraints that require certain linear constraints to hold approximately, to within a specified error bound. The new method is an extension of multisignal relative-entropy spectrum analysis (with exact autocorrelations). The two methods are compared, and connections with previous related work are indicated. Mathematical properties of the new method are discussed, and an illustrative numerical example is presented.

This paper presents results of a new spectrum-analysis method that estimates a number of power spectra when a prior estimate of each is available and new information is obtained in the form of values of the auto-correlation function of their sum. The method applies for instance when one obtains autocorrelation measurements for a signal with independent additive interference, and one has prior estimates of the signal and noise spectra. By incorporating prior estimates for both spectra, the method offers considerable flexibility for tailoring an estimator to the characteristics of a signal or noise. The new method, a generalization of Minimum-Cross-Entropy Spectrum Analysis (MCESA) and Maximum Entropy Spectrum Analysis (MESA), is called Multisignal MCESA. Its theoretical basis is reviewed, and results of experimental tests of an implementation are presented. The test data comprise digitized samples of speech corrupted with helicopter noise and tone interference.

An error in the subject paper is pointed out: when the axioms given there are restricted to the discrete case, they do not imply the discrete case of the principle of minimum cross-entropy. The principle is shown to follow, however, from the adoption of an additional axiom: if new information is consistent with a prior estimate of a probability distribution, then the posterior estimate equals the prior. Minor other improvements and corrections to the arguments in the paper are made.

The principle of minimum cross-entropy (minimum directed divergence, minimum discrimination information) is a general method of inference about an unknown probability density when there exists a prior estimate of the density and new information in the form of constraints on expected values. Various fundamental properties of cross-entropy minimization are proven and collected in one place. Cross-entropy's well-known properties as an information measure are extended and strengthened when one of the densities involved is the result of cross-entropy minimization. The interplay between properties of cross-entropy minimization as an inference procedure and properties of cross-entropy as an information measure is pointed out. Examples are included and general analytic and computational methods of finding minimum cross-entropy probability densities are discussed.

Jaynes's principle of maximum entropy and Kullbacks principle of minimum cross-entropy (minimum directed divergence) are shown to be uniquely correct methods for inductive inference when new information is given in the form of expected values. Previous justifications use intuitive arguments and rely on the properties of entropy and cross-entropy as information measures. The approach here assumes that reasonable methods of inductive inference should lead to consistent results when there are different ways of taking the same information into account (for example, in different coordinate system). This requirement is formalized as four consistency axioms. These are stated in terms of an abstract information operator and make no reference to information measures. It is proved that the principle of maximum entropy is correct in the following sense: maximizing any function but entropy will lead to inconsistency unless that function and entropy have identical maxima. In other words given information in the form of constraints on expected values, there is only one (distribution satisfying the constraints that can be chosen by a procedure that satisfies the consistency axioms; this unique distribution can be obtained by maximizing entropy. This result is established both directly and as a special case (uniform priors) of an analogous result for the principle of minimum cross-entropy. Results are obtained both for continuous probability densities and for discrete distributions.

The above \fbox{paper\1}% proposes a method for choosing prior probability distributions by finding the rain-max of an uncertainty functional that obeys certain axioms. Several functionals are exhibited here that obey the axioms, but do not belong to the family considered in the paper and are thus counterexamples to theorems in the paper asserting the uniqueness of the functionals. Errors in the former proofs are pointed out, possible corrections are discussed, and a lemma is corrected.

The directed divergences of two probability densitiespandqare given by\int p(x) \log (p(x)/q(x))dxand by the same expression withpandqinterchanged; the divergence is the sum of the directed divergences. These quantities have applications in information theory and to the problem of assigning prior probabilities subject to constraints. It is shown that the directed divergences and their positive linear combinations, including the divegeoce, are characterized by axioms of \it{positivity, additivity}, and \it{finiteness}, which are fundamental in work on prior probabilities. In the course of the proof, the latter two are shown to imply yet another axiom: \it{linear invariance}.