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

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

11 Citationer (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.

Originalsprog	Engelsk
Titel	Mathematical Foundations of Computer Science 1981 : Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981
Redaktører	Jozef Gruska, Michal Chytil
Antal sider	8
Forlag	Springer
Publikationsdato	1981
Sider	132-139
DOI	https://doi.org/10.1007/3-540-10856-4_79
Status	Udgivet - 1981
Begivenhed	Symposium on Mathematical Foundations of Computer Science - Strbske Pleso, Czechoslovakia, Tjekkiet Varighed: 31 aug. 1981 → 4 sep. 1981 Konferencens nummer: 10th

Konference

Konference	Symposium on Mathematical Foundations of Computer Science
Nummer	10th
Land/Område	Tjekkiet
By	Strbske Pleso, Czechoslovakia
Periode	31/08/1981 → 04/09/1981

Navn	Lecture Notes in Computer Science
Vol/bind	118

Adgang til dokumentet

10.1007/3-540-10856-4_79

Biblioteksadgang?

Tjek tilgængelighed hos det Kgl. Bibliotek

Citationsformater

@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. i J Gruska & M Chytil (red), Mathematical Foundations of Computer Science 1981: Proceedings, 10th Symposium Štrbské Pleso, Czechoslovakia August 31 – September 4, 1981. Springer, Lecture Notes in Computer Science, bind 118, s. 132-139, Symposium on Mathematical Foundations of Computer Science, Strbske Pleso, Czechoslovakia, Tjekkiet, 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. red. / Jozef Gruska; Michal Chytil. Springer, 1981. s. 132-139 (Lecture Notes in Computer Science, Bind 118).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Adgang til dokumentet

Biblioteksadgang?

Fingeraftryk

Citationsformater