SOME RESULTS IN ALGEBRAIC COMPLEXITY THEORY.

Title: SOME RESULTS IN ALGEBRAIC COMPLEXITY THEORY.
Identifier: AAI8023667
identifier: 8023667
Creator: FEIG, EPHRAIM.
Contributor: Louis Auslander | Shmuel Winograd
Date: 1980
Language: English
Publisher: City University of New York.
Subject: Mathematics
Abstract: In this paper we investigate certain sets of semilinear and bilinear forms. We show that computing the Fourier Transform on the group Z/pZ (CRPLUS). . . . . .(CRPLUS) Z/pZ is rationally equivalent to computing a direct sum system of semilinear forms, where each direct summand can be viewed as an element in some cyclotomic extension field. We show that the bilinear multiplicative complexity of computing the products ab(,1), . . ., ab(,k), where a, b(,1), . . . , b(,k) are arbitrary elements in a quadratic extension field, is 3k. We prove that every minimal division-free algorithm for computing the product of two arbitrary elements in a finite algebraic extension field is bilinear. We prove that the multiplicative complexity of the quaternion product over a real field is 8.
Type: dissertation
Source: PQT Legacy CUNY.xlsx
degree: Ph.D.
Program: Mathematics