On parallel evaluation of certain classes of polynomials with an increasing number of variables
type: Item
instance of: scholarly article
title: On parallel evaluation of certain classes of polynomials with an increasing number of variables
zbMATH Open document ID: 0727.68036
published in: Moscow University Mathematics Bulletin
publication date: 1990-01-01T00:00:00Z
review text: In this paper we shall evaluate polynomials with integral coefficients by formulas in the basis \(B=\{xy,x\pm y,1\}\). We introduce the concept of a formula by induction as follows. (1) A formula of depth 1 and complexity 1 is a symbol of variables or is a basis constant equal to 1. (2) If \(\Phi_ 1\) and \(\Phi_ 2\) are two formulas of depth \(D_ 1\) and \(D_ 2\) and of complexity \(L_ 1\) and \(L_ 2\), respectively, then \((\Phi_ 1\circ \Phi_ 2)\) is a formula of depth \([1+\max (D_ 1,D_ 2)]\) and complexity \([L_ 1+L_ 2+1]\), where the symbol \(\circ\) stands for multiplication, addition or substraction \((\cdot,+,-).\) Let L(f) and D(f) denote the minimal complexity and minimal depth of formulas realizing a polynomial f. The depth D(f) can be interpreted as the time required to compute the polynomial f by an indefinite number of processors which execute arithmetic operations over natural numbers (under the assumption that computation time does not depend on the operation type and magnitude of the operands). Consider the class \({\mathcal P}_ c(d)\) consisting of all polynomials with coefficients 0,1,...,c and of degrees \(d_ i\) in the variables \(x_ i\), where \(d=(d_ 1,d_ 2,...d_ n)\). Let us put L(\({\mathcal P}_ c(d))=\max \{L(f):\) \(f\in {\mathfrak P}_ c(d)\}\), D(\({\mathcal P}_ c(d))=\max \{D(f):f\in {\mathcal P}_ c(d)\}.\) Then the following assertion holds: Let n tend to infinity. Then L(\({\mathcal P}_ c(d))\sim H/\log_ 2n\) and for \(d_ 1+...+d_ n+\log c=2^{O(n/\log n)},\) the following equality holds: \[ D({\mathcal P}_ 1(d))=\log_ 2H-\log_ 2\log_ 2n+O(1), \] where \(H=(d_ 1+1)...(d_ n+1)\log (c+1)\).
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 4201611
zbMATH Keywords: complexity of formulas
zbMATH Keywords: parallel evaluation
zbMATH Keywords: depth of formulas
author: S. B. Gashkov
MaRDI profile type: MaRDI publication profile
description: scientific article; zbMATH DE number 4201611