✦ LIBER ✦

Fast parallel algorithms for Graeffe's root squaring technique

✍ Scribed by P.K. Jana; B.P. Sinha

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 476 KB
Volume: 35
Category: Article
ISSN: 0898-1221
DOI: 10.1016/s0898-1221(97)00280-0

No coin nor oath required. For personal study only.

✦ Synopsis

This paper presents two parallel algorithms for the solution of a polynomial equation of degree n, where n can be very large. The algorithms are based on Graeffe's root squaring technique implemented on two different systolic architectures, built around mesh of trees and multitrees, respectively. Each of these algorithms requires O(log n) time using O(n 2) processors.

geywords--Root extraction, Graeffe's root squaring method, Matrix-vector multiplication, Mesh of trees, Multitrees.

📜 SIMILAR VOLUMES

Square-root algorithms for parallel proc

Square-root algorithms for parallel processing in optimal estimation

✍ M. Morf; J.R. Dobbins; B. Friedlander; T. Kailath 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 707 KB

Explicit square-root algorithms allow measurements for the standard state estimation problem to be processed in parallel with little communication between processors. A particular consequence is the development of compact square-root doubling formulae.

Discussion of ‘square root algorithms fo

Discussion of ‘square root algorithms for parallel processing in optimal estimation’

✍ Donald J. Schmidt 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 97 KB

Fast parallel algorithms for forecasting

✍ P.K. Jana; B.P. Sinha 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 540 KB

This paper presents two parallel algorithms for forecasting implemented on a linear array and a tree model [1]. Both the algorithms are based on the weighted moving average technique [2,3]. Given that m and n are the numbers of the input observed data values and the numbers of weights, respectively,

Reply to discussion of ‘square-root algo

Reply to discussion of ‘square-root algorithms for parallel processing in optimal estimation’

✍ M. Morf; T. Kailath; J.R. Dobbins; B. Friedlander; J. Newkirk 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 107 KB

Multilevel fast multipole algorithm enha

Multilevel fast multipole algorithm enhanced by GPU parallel technique for electromagnetic scattering problems

✍ Kan Xu; Da Zhi Ding; Zheng Hong Fan; Ru Shan Chen 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB

## Abstract Along with the development of graphics processing Units (GPUS) in floating point operations and programmability, GPU has increasingly become an attractive alternative to the central processing unit (CPU) for some of compute‐intensive and parallel tasks.In this article, the multilevel fa

Fast and Scalable Parallel Algorithms fo

Fast and Scalable Parallel Algorithms for Knapsack-like Problems

✍ Afonso Ferreira; John Michael Robson 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 403 KB

We present two new algorithms for searching in sorted X ؉ Y ؉ R ؉ S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n 2 log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n ‫؍‬ O(2 s/4 ), we obtain a