Topics in computational complexity and the analysis of algorithms

62. R. P. Brent, Topics in computational complexity and the analysis of algorithms, Report TR-CS-80-14, Department of Computer Science, ANU, October 1980, 375  pp.

Abstract

[From the Introduction]

The theme of this collection of papers is the derivation of rigorous bound on the cost of certain computations. Cost may be measured in several different ways. For example, in [37, 39, 45, 50] we identify cost with the number of arithmetic operations performed on integers or real numbers, in [32, 34] we consider the number of Boolean operations, and in [12, 14, 16] we count function and derivative evaluations. In [3, 15, 18, 22] it is more appropriate to consider the time required to evaluate an expression on a parallel machine, and in [55, 60] we introduce an area-time product which is motivated by practical cost measures for VLSI circuits.

Most of the papers are concerned with upper bounds, which are established by exhibiting an algorithm and analysing its performance. In [16, 55] nontrivial lower bounds are established. Proofs of lower bounds are generally more difficult than those for upper bounds, since it is necessary to consider all possible algorithms for the problem at hand, rather than just one carefully selected algorithm. The aim when establishing upper and lower bounds is, of course, to bring them as close together as possible, but this is difficult unless the "trivial" lower bound is almost attainable, as in [3].

The collection is divided into the following sections.

  1. Introduction and bibliography.
  2. Parallel evaluation of arithmetic expressions [15, 22, 18].
  3. Circuits for arithmetic operations [3, 60, 55].
  4. Continuous models for discrete algorithms [37, 13].
  5. Algorithms for manipulating formal power series [45, 39, 50].
  6. The complexity of algorithms for solving nonlinear equations [16, 27, 12, 14].
  7. Asymptotically fast algorithms for high-precision computations [28, 32, 34].

Comments

This is a selection of papers submitted for the degree of Doctor of Science at Monash University (degree awarded 1981).

The papers included are [3, 12, 13, 14, 15, 16, 18, 22, 27, 28, 32, 34, 37, 39, 45, 50, 55, 60].

Acknowledgement

Thanks to David Kuck, H. T. Kung, Kiyoshi Maruyama, Joe Traub, Shmuel Winograd and Phil Wolfe for permission to include some of our joint papers in this collection. Specifically, these joint papers are:

Excerpts

These are gif page images, mainly 768×1056 pixels:
rubber stamp;
title page;
copyright notice;
acknowledgements;
contents;
introduction: 9, 10, 11, 12, 13, 14;
bibliography: 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26.

other sections: see the papers mentioned in the abstract above.

All the above gif files are available in a single pdf file (1346K).

Go to next publication

Return to Richard Brent's index page