More Web Proxy on the site http://driver.im/

article

Free access

Restructuring of Arithmetic Expressions For Parallel Evaluation

Authors:

David E. Muller,

Franco P. PreparataAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 534 - 543

https://doi.org/10.1145/321958.321973

Published: 01 July 1976 Publication History

Abstract

Let E be an arithmetic expression involving n variables, each of which appears just once, and the possible operations of addition, multiplication, and division. Although other cases are considered, when these three operations take unit time the restructuring algorithms presented in this paper yield evaluation times no greater than 2.88 log₂n + 1 and 2.08 log₂n for general expressions and division-free expressions, respectively. The coefficients are precisely given by 2/log₂α ≈ 2.88 and 1/log₂β ≈ 2.08, where α and β are the positive real roots of the equations z² = z + 1 and z⁴ = 2z + 1, respectively. While these times were known to be of order log₂n, the best previously known coefficients were 4 and 2.15 for the two cases.

The authors conjecture that the present coefficients are the best possible, since they have exhibited expressions which seem to require these times within an additive constant.

The paper also gives upper bounds to the restructuring time of a given expression E and to the number of processors required for its parallel evaluation. It is shown that at most O(n^1.44) and O(n^1.82) operations are needed for restructuring general expressions and division-free expression, respectively.

It is pointed out that, since the order of the compiling time is greater than n log n, the numbers of required processors exhibit the same rate of growth in n as the corresponding compiling times.

References

[1]

BERLEKAMP, E R Algebrazc Coding Theory. McGraw-Hill, New York, 1968

[2]

BERLEKAMP, E.R. Factoring polynomzals over large finite fields Math. Comput 24, 111 (July 1970), 713-735

[3]

CHARLETON, R T A Pascal ~mplementatlon of algorithms for the factorizatlon and greatest common diwsor calculatma of multivariate polynomJals. Master's Th, U. of Texas, Austin, Texas, Aug 1973

[4]

COLLINS, GEOROE E The SAC-1 system An mtroductlon and survey Proc Second Symp on Symbohc and Algebraic Mampulatlon (ACM), Los Angeles, Cahf, March 1971, pp 144--152

[5]

COLLJNS, G. E Computer algebra of polynomials and rationM functions. Amer. Math Mon. 80, 7 (Aug-Sept 1973), 725-755

[6]

COLLINS, GEORGE E, HEINDEL, L E, }-IoRowITz, E, MCCLELLAN, M T, AND MUSSER, D R. The SAC-1 modular arithmetic system. Tech Rep. No. 10, U of Wisconsin, Madison, Wlsc, June 1969.

[7]

COLLINS, GEORGE E, AND MVSSER, D R. The SAC-1 polynomial factorizat,on system Comput. Scmnces Tech Rep No 157, U of Wisconsin, Madison, Wlsc, March 1972

[8]

FLOYD, ROBERT W. Assigning meamngs to programs Proc of a Symp in Apphed Mathematics, Vol. 19. Mathematical Aspects of Computer Scmnce, J. T Schwartz, Ed, Amer Math Soc, Providence, R I, 1967, pp 19-32

[9]

GELFOND, A O. Transcendental and Algebraic Numbers Dover, New York, 1960.

[10]

HOROWITZ, ELLIS Algorithms for symbohc integratmn of ratmnal functions Ph D. Th, Comput Scmnces Dep, U of WlsconsJn, Madison, Wlsc, 1969

[11]

KNUTH, DONALD E The Art of Computer Programming, Vol. I Fundamental Algomthms Addison-Wesley, Reading, Mass, 1968

[12]

KNUTS, DONALD E The Art of Computer Programmzng, Vol II. Semznumer~cal Algomthms Addison-Wesley, Reading, Mass, 1969

[13]

MIGNOTTE, M An,nequahty about factors of polynomials Math Comput (to appear)

[14]

MUSSER, D R Algorithms for polynomial factonzation Tech Rep No 134 (Ph D Th ), Comput Sciences Dep, U of Wisconsin, Madison, Wlsc., Sept 1971

[15]

RAn~N, MICHAEL O Computable algebra, general theory and theory of computable fields Trans Amer Math Soc ~5 (1960),341-360

[16]

VAN DER WAERDEN, B L Modern Algebra, Vol I (transl by Fred Blum). Ungar, New York, 1949{

[17]

WANG, PA~L S, AND ROTHCHILD, L PREISS Factormg mult~var,ate polynomials over the integers ACM SIGSAM Bull No 28, Dec 1973

[18]

ZASSr~SH.~US, HANS On Hensel factorlzatlon, I J Numer Theory I (1969), 291-311.

Cited By

Heller D(2020)A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review10.1137/102009620:4(740-777)Online publication date: 30-Jun-2020
https://dl.acm.org/doi/10.1137/1020096
Sergeev I(2020)On a Relation Between the Depth and Complexity of Monotone Boolean FormulasJournal of Applied and Industrial Mathematics10.1134/S199047891904016113:4(746-752)Online publication date: 4-Feb-2020
https://doi.org/10.1134/S1990478919040161
Poizat B(2014)A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de ValiantThe Journal of Symbolic Logic10.2178/jsl/123039691373:04(1179-1201)Online publication date: 12-Mar-2014
https://doi.org/10.2178/jsl/1230396913
Show More Cited By

Index Terms

Restructuring of Arithmetic Expressions For Parallel Evaluation
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Arbitrary-precision arithmetic
      2. Interval arithmetic
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

The Parallel Evaluation of General Arithmetic Expressions

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₂n + 10(n - 1)/p using p ≥ 1 processors which can ...
Time Bounds on the Parallel Evaluation of Arithmetic Expressions

This paper presents a number of bounds on the parallel processor evaluation of arithmetic expressions. Several previous papers show that if the evaluation of an expression using a serial computer requires t operations, by using a number of processors in ...
Genome-wide co-expression based prediction of differential expressions

Motivation: Microarrays have been widely used for medical studies to detect novel disease-related genes. They enable us to study differential gene expressions at a genomic level. They also provide us with informative genome-wide co-expressions. Although ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
438
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Heller D(2020)A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review10.1137/102009620:4(740-777)Online publication date: 30-Jun-2020
https://dl.acm.org/doi/10.1137/1020096
Sergeev I(2020)On a Relation Between the Depth and Complexity of Monotone Boolean FormulasJournal of Applied and Industrial Mathematics10.1134/S199047891904016113:4(746-752)Online publication date: 4-Feb-2020
https://doi.org/10.1134/S1990478919040161
Poizat B(2014)A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de ValiantThe Journal of Symbolic Logic10.2178/jsl/123039691373:04(1179-1201)Online publication date: 12-Mar-2014
https://doi.org/10.2178/jsl/1230396913
Poizat B(2014)Malod and the PascalinePerspectives in Computational Complexity10.1007/978-3-319-05446-9_8(147-157)Online publication date: 17-Jul-2014
https://doi.org/10.1007/978-3-319-05446-9_8
Poizat B(2010)Une dualité entre fonctions booléennesJournal of the Institute of Mathematics of Jussieu10.1017/S14747480100000839:03(633-652)Online publication date: 26-Apr-2010
https://doi.org/10.1017/S1474748010000083
Rautenbach DSzegedy CWerber J(2007)The delay of circuits whose inputs have specified arrival timesDiscrete Applied Mathematics10.1016/j.dam.2006.10.013155:10(1233-1243)Online publication date: 21-May-2007
https://dl.acm.org/doi/10.1016/j.dam.2006.10.013
von zur Gathen J(2005)Parallel arithmetic computations: A surveyMathematical Foundations of Computer Science 198610.1007/BFb0016236(93-112)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0016236
Pardo L(2005)How lower and upper complexity bounds meet in elimination theoryApplied Algebra, Algebraic Algorithms and Error-Correcting Codes10.1007/3-540-60114-7_4(33-69)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-60114-7_4
Dekel ENtafos SPeng S(2005)Parallel tree techniques and code optimizationVLSI Algorithms and Architectures10.1007/3-540-16766-8_18(205-216)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-16766-8_18
Commentz-Walter B(2005)Size — Depth tradeoff in boolean formulasAutomata, Languages and Programming10.1007/3-540-08860-1_11(125-141)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-08860-1_11
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents