Some linear-time algorithms for systolic arrays

Details Some linear-time algorithms for systolic arrays Some linear-time algorithms for systolic arrays

2010-04-21

arxiv.org/abs/1004.3716v1

Information Processing 83 (edited by R.E.A. Mason), North-Holland, Amsterdam, 1983, 865-876

Computer Science

Data Structures and Algorithms

Corrected version of an old (1983) paper. 23 pages. For further details, see http://wwwmaths.anu.edu.au/~brent/pub/pub079.html

Scientific paper

We survey some results on linear-time algorithms for systolic arrays. In particular, we show how the greatest common divisor (GCD) of two polynomials of degree n over a finite field can be computed in time O(n) on a linear systolic array of O(n) cells; similarly for the GCD of two n-bit binary numbers. We show how n * n Toeplitz systems of linear equations can be solved in time O(n) on a linear array of O(n) cells, each of which has constant memory size (independent of n). Finally, we outline how a two-dimensional square array of O(n)* O(n) cells can be used to solve (to working accuracy) the eigenvalue problem for a symmetric real n* n matrix in time O(nS(n)). Here S(n) is a slowly growing function of n; for practical purposes S(n) can be regarded as a constant. In addition to their theoretical interest, these results have potential applications in the areas of error-correcting codes, symbolic and algebraic computations, signal processing and image processing.

Affiliated with

Also associated with

No associations

Rating

Some linear-time algorithms for systolic arrays does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some linear-time algorithms for systolic arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some linear-time algorithms for systolic arrays will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327282