A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.

We outline some of Chris Wallace's contributions to pseudo-random number generation. In particular, we consider his idea for generating normally distributed variates without relying on a source of uniform random numbers, and compare it with more conventional methods for generating normal random numbers. Implementations of Wallace's idea can be very fast (approximately as fast as good uniform generators). We discuss the statistical quality of the output, and mention how certain pitfalls can be avoided.

An interesting and important, hut largely ignored question associated with the ML method is whether there exists only a single maximum likelihood point for a given phylogenetic tree. Mike Steel presented a simple analytical result to argue that the ML point is not unique. However, his view so far attracts only little attention. Though many researchers believe that multiple maximum likelihood points may exist for certain phylogenetic trees, most existing phylogenetic construction programs only produce a single best tree under the ML criterion and in practice many researchers still use only the ML values to make judgment on the quality of different trees for a given problem. In this paper we present some experimental results from a large number of synthetic test data sets and show that it is quite common that certain incorrect trees can have likelihood values at least as large as that of the correct tree. A significant implication of this is that even if we are able to find a truly globally optimal tree under the maximum likelihood criterion, this tree may not necessarily be the correct phylogenetic tree. In the paper we also show that our newly developed algorithm can perform much better in terms of accuracy than well known algorithms such as FASTDNAML and PHYML by constructing only a few more trees for a given problem

This paper describes a parallel implementation of our recently developed algorithm for phylogenetic analysis on the IBM BlueGene/L cluster. This algorithm constructs evolutionary trees for a given set of DNA or protein sequences based on the topological information of every possible quartet trees. Our experimental results showed that it has several advantages over many popular algorithms. By distributing the quartet weights evenly across the processing nodes and making effective use of a fast collective network on the IBM BlueGene/L cluster, we are able to achieve a close to linear speedup even when the number of processors involved in the computation is large.

In this paper we introduce a new quartet-based method. This method makes use of the Bayes (or quartet) weights of quartets as those used in the quartet puzzling. However, all the weights from the related quartets are accumulated to form a global quartet weight matrix. This matrix provides integrated information and can lead us to recursively merge small sub-trees to larger ones until the final single tree is obtained. The experimental results show that the probability for the correct tree to be among a very small number of trees constructed using our method is very high. These significant results open a new research direction to further investigate more efficient algorithms for phylogenetic inference.

Motivated by a connection with block iterative methods for solving linear systems over finite fields, we consider the probability that the Krylov space generated by a fixed linear mapping and a random set of elements in a vector space over a finite field equals the space itself. We obtain an exact formula for this probability and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.

Applying gang scheduling can alleviate the blockade problem caused by exclusively space-sharing scheduling. To simply allow jobs to ran simultaneously on the same processors as in conventional gang scheduling, however, may introduce a large number of time slots in the system. In consequence the cost of context switches will be greatly increased, and each running job can only obtain a small portion of resources including memory space and processor utilisation and so no jobs can finish their computations quickly. Therefore, the number of jobs allowed to run in the system should be limited. In this paper we present some experimental results to show that by limiting real large jobs time-sharing the same processors and applying the backfilling technique we can greatly reduce the average number of time slots in the system and significantly improve the performance of both small and large jobs.

Given a graph G=(V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of G in the parallel setting for k=2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: (1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n/sup 3/4/) processors per update and query. (2) It is shown that the biconnectivity problem can be solved in O(log/sup 2 n/) time using O(n/spl alpha/(2n, n)/logn) processors per update and O(1) time with a single processor per query or in O(log n log/sub n///sup m/) time using O(n/spl alpha/(2n, n)/log n) processors per update and O(logn) time using O(n/spl alpha/(2n, n)/logn) processors per query, where /spl alpha/(.,.) is the inverse of Ackermann's function. (3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log/sub n///sup m/+logn log log n//spl alpha/(3n, n)) time using O(n/spl alpha/(3n, n)/log n) processors per update and O(1) time with a single processor per query. (4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to /spl Omega/(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n/sup 3/4/) processors. All the proposed algorithms run on a CRCW PRAM.

... Project is a joint research program involving staff at the Aus-tralian National University and Fujitsu Japan. The aim of the project is to produce a library of mathematical subrou-tines for the vector-parallel Fujitsu VPP300 which result in high performance and accuracy on large problems. In order to utilise the architecture of the VPPSOO it is necessary to develop new algorithms for many of the standard numerical problems.

There has recently been an interest in the introduction of reconfigurable buses to existing parallel architectures. Among them Reconfigurable Mesh (RM) draws much attention because of its simplicity. This paper presents two O(1) time algorithms to compute the contour of the maximal elements of N planar points on the RM. The first algorithm employs an RM of size N/spl times/N while the second one uses a 3-D RM of size /spl radic/N/spl times//spl radic/N/spl times//spl radic/N.

The problem of merging two sequences of elements which are stored separately in two processing elements (PEs) occurs in the implementation of many existing sorting algorithms. We describe efficient algorithms for the merging problem on asynchronous distributed-memory machines. The algorithms reduce the cost of the merge operation and of communication, as well as partly solving the problem of load balancing. Experimental results on a Fujitsu AP1000 are reported.

A parallel sorting algorithm is presented for storage-efficient internal sorting on MIMD machines. The algorithm first sorts the elements within each node using a serial based algorithm, then a two-phase parallel merge. It requires additional storage of order of the square root of the number of elements in each node. Performance of the algorithm on two general-purpose MIMD machines, the Fujitsu AP1000 and the Thinking Machines CM5, is examined. The algorithm is suitable for implementation on special-purpose parallel machines, e.g., parallel database machines.>

We describe a new Jacobi ordering for parallel computation of SVD problems. The ordering uses the high bandwidth of a perfect binary fat-tree to minimise global interprocessor communication costs. It can thus be implemented efficiently on fat-tree architectures.

A stabilized parallel algorithm for direct-form recursive filters is obtained, using a method of derivation in the Z domain. The degree of parallelism, stability, and complexity of the algorithm is examined. It is shown how to reduce the number of multiplications compared to the number required in a naive implementation. The algorithm is regular and modular, so very efficient VLSI architectures can be constructed to implement it. The degree of parallelism in these implementations can be chosen freely and is not restricted to be a power of two.>

An algorithm that is faster than back-propagation and for which it is not necessary to specify the number of hidden units in advance is described. The relationship with other fast pattern-recognition algorithms, such as algorithms based on k-d trees, is discussed. The algorithm has been implemented and tested on artificial problems, such as the parity problem, and on real problems arising in speech recognition. Experimental results, including training times and recognition accuracy, are given. Generally, the algorithm achieves accuracy as good as or better than nets trained using back-propagation. Accuracy is comparable to that for the nearest-neighbor algorithm, which is slower and requires more storage space.

We present a linearly connected array of O(n) cells that solves the linear least-squares problem for an (m + 1) × (n + 1) Toeplitz matrix in time O(m + n). The total storage required is O(n) words, i.e., only a constant per cell. The parallel algorithm described in this paper is based on the sequential QR factorization algorithm for Toeplitz matrices recently developed by the authors.

We describe an algorithm that efficiently implements the first-fit strategy for dynamic storage allocation. The algorithm imposes a storage overhead of only one word per allocated block (plus a few percent of the total space used for dynamic storage), and the time required to allocate or free a block is O (log W ), where W is the maximum number of words allocated dynamically. The algorithm is faster than many commonly used algorithms, especially when many small blocks are allocated, and has good worst-case behavior. It is relatively easy to implement and could be used internally by an operating system or to provide run-time support for high-level languages such as Pascal and Ada. A Pascal implementation is given in the Appendix.

The authors introduce a high-throughput systolic implementation of the direct-form second-order recursive filter. The systolic structure has the advantage of regularity over implementations of the block-state-variable form. Since communication is very expensive in VLSI implementations in terms of area, as well as time, this regular structure is considered better for VLSI than those based on block-state-variable filter descriptions.>

It is shown that the greatest common divisor of two n-bit integers (given in the usual binary representation) can be computed in time O(n) on a linear systolic array of O(n) identical cells.

The problem of finding a greatest common divisor (GCD) of any two nonzero polynomials is fundamental to algebraic and symbolic computations, as well as to the decoder implementation for a variety of error-correcting codes. This paper describes new systolic arrays that can lead to efricient VLSI solutions to both the GCD problem and the extended GCD problem.

No abstract available.

Area-time bounds on VLSI circuits for context-free language recognition, for the evaluation of propositional calculus formulae and for set equality and disjointness questions, are considered. In all cases, a lower bound $AT^{2\alpha } = \Omega (n^{1 + \alpha } )$ is proved, where A is the chip area, T the execution time, and $0 \leqq \alpha \leqq 1$. Similar results were known for computations with $\Omega (n)$-bit outputs, but the computations considered here have only 1-bit outputs. Upper bounds are also discussed.

With VLSI architecture, the chip area and design regularity represent a better measure of cost than the conventional gate count. We show that addition of n-bit binary numbers can be performed on a chip with a regular layout in time proportional to log n and with area proportional to n.

The problem of performing multtphcaUon of n-bit binary numbers on a chip is considered Let A denote the ch~p area and T the time reqmred to perform mult~phcation.By using a model of computation which is a realistic approx~mauon to current and anucipated LSI or VLSI technology, ~t is shown thatfor all a ~ [0, 1], where A0 and To are posmve constants which depend on the technology but are mdependent of n.The exponent 1 + a is the best possible A consequence of this result is that binary multiphcatlon is "harder" than binary addmon More precisely, ff(AT2~)M(n) and (AT2~)A(n) denote the mmimum area-time complexity for n-b~t binary multiphcauon and addmon, respectively, then (AT2~)M(n) _ 1 f~(nl-a) for 0 _< a --< na for ~ ,(= fi(nl/2) for all a _> 0).

The chip complexity of a computation is concerned with the chip area, A, and the time, T, required to perform the computation when implemented on a chip. An area-time product ATα,for α ≥ 0, is used as a complexity measure. A particular value of α, which is chosen by the user, reflects the relative importance between A and T. This paper derives lower and upper bounds on the area-time complexity for chips that implement binary arithmetic, assuming a model of computation which is intended to approximate, current and anticipated LSI or VLSI technology.

Let $F(x) = f_1 x + f_2 x^2 + \cdots $ be a formal power series over a field $\Delta $ Let $F^{[0]} (x) = x$ and for $q = 1,2, \cdots $ , define $F^{[q]} (x) = F^{[q - 1]} (F(x))$. The obvious algorithm for computing the first n terms of $F^{[q]} (x)$ is by the composition analogue of repeated squaring. This algorithm has complexity about $\log _2 q$ times that of a single composition. Brent showed that the factor $\log _2 q$ can be eliminated in the computation of the first n terms of $(F(x))^q $ by a change of representation, using the logarithm and exponential functions. We show the factor $\log _2 q$ can also be eliminated for the composition problem, unless the complexity of composition is quasi-linear. $F^{[q]} (x)$ can often, but not always, be defined for more general q. We give algorithms and complexity bounds for computing the first n terms of $F^{[q]} (x)$ whenever it is defined. We conclude the paper with some open problems.

The procedure requuced to interface Brent's multiple premsmn package MP with the AUGMENT precompfler for Fortran is described A method of using the multiple preclsmn arithmetm package m conjunctmn with AUGMENT is discussed.

No abstract available.

The classical algorithms require order n ~ operations to compute the first n terms in the reversion of a power series or the composition of two series, and order nelog n operations if the fast Founer transform is used for power series multiplication In this paper we show that the composition and reversion problems are equivalent (up to constant factors), and we give algorithms which require only order (n log n) ~/2 operations In many cases of practical importance only order n log n operations are required, these include certain special functions of power series and power series solution of certain differential equations Applications to root-finding methods which use inverse mterpolauon and to queuemg theory are described, some results on multivariate power series are stated, and several open questions are mentioned KEY WORDS AND PHRASES formal power series, reversion of power series, composition of power series, computational complexity, fast algorithms, special functions of power series, power series solution of dlfferentml equations, queuetng theory, fast Fourier transform CRCATEGORIES 57,5 15,5 17 IntroductionWe are mterested m the complexity of algorithms for mampulatlng formal power series.For example, such algorithms may compute the first n terms in the product, quotient, or composition of two gwen power series.These problems arise in combmatorics and analysis of algorithms, where the desired power series is a generating function, as well as in numerical analysis.See, for example, Knuth [26], Ferguson, Nielsen, and Cook [14], Riordan [35], Gilbert [18], Nwen [31], Jackson and Reilly [25], Levy and Lessman [30], Norman [32], and Henrici [20, 21].Let ~ be the integral domain of formal power series P(s) = po + p~s + p2s 2 + over some field K "Formal" means that we are not concerned with questions of convergence.If F is a set of indetermmates over K, and E is a finite subset of the extension field K(F), then L(E mod F) denotes the number of operations necessary to compute E, starting from K U F and working in K(F).Informally, L(E rood F) is the number of operations required to compute E, given F. If A, B E @ and C is the formal product of A and B, we define M(n) = L(¢o ..... cn mod a0 ..... an, b0 ..... b,,) Informally, M(n) is the number of operations required to compute the

A collection of ANSI Standard Fortran subroutines for performing multiple-precision floatingpoint arithmetic and evaluating elementary and special functions is described.The subroutines are machine independent and the precision is arbitrary, subject to storage limitations.The design of the package is discussed, some of the algomthms are described, and test results are given.

The design of the package and the theoretical background for the algorithms used are given in [1].Details of calling sequences, etc., are given in the comments included here and in [2]. ALGORITHM[Only that portion of the listing which gives the introductory comments and a small example program is printed here.The complete listing, together with a Users' Guide giving further details, is available from the AC5~I Algorithms Distribution Service (see inside back cover for order form).]

Let ƒ( x ) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M ( n ) be the number of single-precision operations required to multiply n -bit integers. It is shown that ƒ( x ) can be evaluated, with relative error Ο (2 - n ), in Ο ( M ( n )log ( n )) operations as n → ∞, for any floating-point number x (with an n -bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on M ( n ), it follows that an n -bit approximation to ƒ( x ) may be evaluated in Ο ( n log 2 ( n ) log log( n )) operations. Special cases include the evaluation of constants such as π, e , and e π . The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.

It is shown that arithmetic expressions with n ≥ 1 variables and constants; operations of addition, multiplication, and division; and any depth of parenthesis nesting can be evaluated in time 4 log 2 n + 10( n - 1)/ p using p ≥ 1 processors which can independently perform arithmetic operations in unit time. This bound is within a constant factor of the best possible. A sharper result is given for expressions without the division operation, and the question of numerical stability is discussed.

For scientific computations on a digital computer the set of real numbers is usually approximated by a finite set F of ``floating-point'' numbers. We compare the numerical accuracy possible with different choices of F having approximately the same range and requiring the same word length. In particular, we compare different choices of base (or radix) in the usual floating-point systems. The emphasis is on the choice of F, not on the details of the number representation or the arithmetic, but both rounded and truncated arithmetic are considered. Theoretical results are given, and some simulations of typical floating-point computations (forming sums, solving systems of linear equations, finding eigenvalues) are described. If the leading fraction bit of a normalized base-2 number is not stored explicitly (saving a bit), and the criterion is to minimize the mean square roundoff error, then base 2 is best. If unnormalized numbers are allowed, so the first bit must be stored explicitly, then base 4 (or sometimes base 8) is the best of the usual systems.

For scientific computations on a digital computer the set of real numbers is usually approximated by a finite set F of “floating-point numbers”. We compare the numerical accuracy possible with different choices of F having approximately the same range and requiring the same wordlength. In particular, we compare different choices of base (or radix) with the usual floating-point systems. The emphasis is on the choice of F, not on the details of the number representation or the arithmetic, but both rounded and truncated arithmetic are considered. Theoretical results are given, and some simulations of typical floating-point computations (forming sums, solving systems of linear equations, finding eigenvalues) are described. If the leading fraction bit of a normalized base-2 number is not stored explicitly (saving a bit), and the criterion is to minimize the mean square roundoff error, then base 2 is best. If unnormalized numbers are allowed, so the first bit must be stored explicitly, then base 4 (or sometimes base 8) is the best of the usual systems.

An algorithm is presented for finding a zero of a function which changes sign in a given interval. The algorithm combines linear interpolation and inverse quadratic interpolation with bisection. Convergence is usually superlinear, and is never much slower than for bisection. ALGOL 60 procedures are given.