Fast parallel computation of polynomials using few processors

Leslie Valiant; Sven Skyum

doi:10.1007/3-540-10856-4_79

Fast parallel computation of polynomials using few processors

Leslie Valiant
, Sven Skyum

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

12 Citations (Scopus)

Abstract

It is shown that any multivariate polynomial that can be computed sequentially in C steps and has degree d can be computed in parallel in 0((log d) (log C + log d)) steps using only (Cd)0(1) processors.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 1981 : Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981
Editors	Jozef Gruska, Michal Chytil
Number of pages	8
Publisher	Springer
Publication date	1981
Pages	132-139
DOIs	https://doi.org/10.1007/3-540-10856-4_79
Publication status	Published - 1981
Event	Symposium on Mathematical Foundations of Computer Science - Strbske Pleso, Czechoslovakia, Czech Republic Duration: 31 Aug 1981 → 4 Sept 1981 Conference number: 10th

Conference

Conference	Symposium on Mathematical Foundations of Computer Science
Number	10th
Country/Territory	Czech Republic
City	Strbske Pleso, Czechoslovakia
Period	31/08/1981 → 04/09/1981

Series	Lecture Notes in Computer Science
Volume	118

Access to Document

10.1007/3-540-10856-4_79

Library access?

Check availability with the Royal Danish Library

Cite this

@inproceedings{c57752507f5b488f9ec8a9faae24b8d2,

title = "Fast parallel computation of polynomials using few processors",

abstract = "It is shown that any multivariate polynomial that can be computed sequentially in C steps and has degree d can be computed in parallel in 0((log d) (log C + log d)) steps using only (Cd)0(1) processors.",

author = "Leslie Valiant and Sven Skyum",

year = "1981",

doi = "10.1007/3-540-10856-4\_79",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "132--139",

editor = "Jozef Gruska and Michal Chytil",

booktitle = "Mathematical Foundations of Computer Science 1981",

address = "Netherlands",

note = "Symposium on Mathematical Foundations of Computer Science ; Conference date: 31-08-1981 Through 04-09-1981",

}

Valiant, L & Skyum, S 1981, Fast parallel computation of polynomials using few processors. in J Gruska & M Chytil (eds), Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981. Springer, Lecture Notes in Computer Science, vol. 118, pp. 132-139, Symposium on Mathematical Foundations of Computer Science, Strbske Pleso, Czechoslovakia, Czech Republic, 31/08/1981. https://doi.org/10.1007/3-540-10856-4_79

Fast parallel computation of polynomials using few processors. / Valiant, Leslie; Skyum, Sven.
Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981. ed. / Jozef Gruska; Michal Chytil. Springer, 1981. p. 132-139 (Lecture Notes in Computer Science, Vol. 118).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Fast parallel computation of polynomials using few processors

AU - Valiant, Leslie

AU - Skyum, Sven

N1 - Conference code: 10th

PY - 1981

Y1 - 1981

N2 - It is shown that any multivariate polynomial that can be computed sequentially in C steps and has degree d can be computed in parallel in 0((log d) (log C + log d)) steps using only (Cd)0(1) processors.

AB - It is shown that any multivariate polynomial that can be computed sequentially in C steps and has degree d can be computed in parallel in 0((log d) (log C + log d)) steps using only (Cd)0(1) processors.

U2 - 10.1007/3-540-10856-4_79

DO - 10.1007/3-540-10856-4_79

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 132

EP - 139

BT - Mathematical Foundations of Computer Science 1981

A2 - Gruska, Jozef

A2 - Chytil, Michal

PB - Springer

T2 - Symposium on Mathematical Foundations of Computer Science

Y2 - 31 August 1981 through 4 September 1981

ER -

Fast parallel computation of polynomials using few processors

Abstract

Conference

Access to Document

Library access?

Fingerprint

Cite this