A chained-matrices approach for parallel computation of continued fractions and its applications

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

A chained-matrices approach for parallel computing the nth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in O(log n) time on the EREW PRAM model or a network with O(n/log n) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as π and e, in O(log m) time by using O(m/log m) processors for a result with m-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general mth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.

Original languageEnglish
Pages (from-to)65-80
Number of pages16
JournalJournal of Scientific Computing
Volume9
Issue number1
DOIs
Publication statusPublished - 1994 Mar 1

Fingerprint

Linear Recurrence
Parallel Computation
Continued fraction
Polynomial Evaluation
Transcendental number
EREW PRAM
Recurrence Equations
Binary trees
Shuffle
Matrix multiplication
Binary Tree
Prefix
Parallel processing systems
Parallel Computing
Hypercube
Digit
Recurrence
Regular hexahedron
Division
Polynomials

Keywords

  • Continued fractions
  • parallel computation
  • parallel-prefix problem
  • polynomial evaluation
  • recurrence equations

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Engineering(all)
  • Computational Theory and Mathematics

Cite this

A chained-matrices approach for parallel computation of continued fractions and its applications. / Lin, Shun-Shii.

In: Journal of Scientific Computing, Vol. 9, No. 1, 01.03.1994, p. 65-80.

Research output: Contribution to journalArticle

@article{b382ad59bb8147e9ad85708ef17b4224,
title = "A chained-matrices approach for parallel computation of continued fractions and its applications",
abstract = "A chained-matrices approach for parallel computing the nth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in O(log n) time on the EREW PRAM model or a network with O(n/log n) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as π and e, in O(log m) time by using O(m/log m) processors for a result with m-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general mth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.",
keywords = "Continued fractions, parallel computation, parallel-prefix problem, polynomial evaluation, recurrence equations",
author = "Shun-Shii Lin",
year = "1994",
month = "3",
day = "1",
doi = "10.1007/BF01573178",
language = "English",
volume = "9",
pages = "65--80",
journal = "Journal of Scientific Computing",
issn = "0885-7474",
publisher = "Springer New York",
number = "1",

}

TY - JOUR

T1 - A chained-matrices approach for parallel computation of continued fractions and its applications

AU - Lin, Shun-Shii

PY - 1994/3/1

Y1 - 1994/3/1

N2 - A chained-matrices approach for parallel computing the nth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in O(log n) time on the EREW PRAM model or a network with O(n/log n) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as π and e, in O(log m) time by using O(m/log m) processors for a result with m-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general mth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.

AB - A chained-matrices approach for parallel computing the nth convergent of continued fractions is presented. The resulting algorithm computes the entire prefix values of any continued fraction in O(log n) time on the EREW PRAM model or a network with O(n/log n) processors connected by the cube-connectedcycles, binary tree, perfect shuffle, or hypercube. It can be applied to approximate the transcendental numbers, such as π and e, in O(log m) time by using O(m/log m) processors for a result with m-digit precision. We also use it to costoptimally solve the second-order linear recurrence, the polynomial evaluation, the recurrence of vector norm, the general class of recurrence equation defined by Kogge and Stone (1973), and the general mth order linear recurrence. It is easy to implement because there are only some matrix multiplications and a division operation involved.

KW - Continued fractions

KW - parallel computation

KW - parallel-prefix problem

KW - polynomial evaluation

KW - recurrence equations

UR - http://www.scopus.com/inward/record.url?scp=0028385358&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028385358&partnerID=8YFLogxK

U2 - 10.1007/BF01573178

DO - 10.1007/BF01573178

M3 - Article

AN - SCOPUS:0028385358

VL - 9

SP - 65

EP - 80

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

SN - 0885-7474

IS - 1

ER -