JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Horowitz, Ellis"
Now showing items 112 of 12

Algorthms for Rational Function Arithmetic Operations
Horowitz, Ellis (Cornell University, 197111)Despite recent advances in speeding up many arithmetic and algebraic algorithms plus an increased concern with algorithm analysis, no computing time study has ever been done for algorithms which perform the rational function ... 
The Application of Symbolic Mathematics to a Singular Perturbation Problem
Horowitz, Ellis (Cornell University, 197202)A basic technique for the numerical solution of ordinary differential equations is to express them as a singular perturbation problem. However, computational studies indicate that the resultant matrix equations which must ... 
Computers and Society: A Proposed Course for Computer Scientists
Horowitz, Ellis; Morgan, Howard L.; Shaw, Alan C. (Cornell University, 197106)The purpose of this paper is to describe a course concerned with both the effects of computers on society and the responsibilities of computer scientists to society. The impact of computers is divided into five components: ... 
Computing Partitions with Applications to the Knapsack Problem
Horowitz, Ellis; Sahni, Sartaj (Cornell University, 197207)Given $r$ numbers $s_{1}, \ldots, s_{r}$, algorithms are investigated for finding all possible combinations of these numbers which sum to $M$. This problem is a particular instance of the 01 unidimensional knapsack problem. ... 
The Efficient Calculation of Powers of Polynomials
Horowitz, Ellis (Cornell University, 197204)Suppose we are given a polynomial $P(x_{1},\ldots,x_{r})$ in $r \geq 1$ variables, let $m$ bound the degree of $P$ in all variables $x_{i}, l \leq i \leq r$, and we wish to raise $P$ to the $n^{th}$ power, $n>1$. In a ... 
A Fast Method for Interpolating Preconditioning
Horowitz, Ellis (Cornell University, 197112)Given $n$ points $(x_{i},y_{i})$ the best algorithms for finding the unique interpolating polynomial $G(x)$ such that $G(x_{i})=y_{i}$ take $O(n^{2})$ arithmetic operations. If the $(x_{i}$ are known in advance then an ... 
On Computing the Determinant of Matrices with Polynomial Entries
Horowitz, Ellis; Sahni, Sartaj (Cornell University, 197307)We consider the problem of computing the determinant of a matrix of polynomials. Four algorithms are compared: expansion by minors, Gaussian elimination over the integers, a method based on evaluation and interpolation, ... 
On Decreasing the Computing Time for Modular Arithmetic
Heindel, Lee E.; Horowitz, Ellis (Cornell University, 197109)In this paper it is shown that by suitably modifying Garner's algorithm for applying the Chinese Remainder Theorem to optimally employ the fast multiplication techniques of Schonhage and Strassen, one can often decrease ... 
On the Computation of Powers of a Class of Polynomials
Horowitz, Ellis; Sahni, Sartaj (Cornell University, 197208)A general class of polynomials is defined which includes as subcases sparse and dense polynomials. For any polynomial $P$ within this class a host of algorithms are analyzed for computing $P^{n}$. While the Homomorphism ... 
On the Substitution of Polynomial Forms
Horowitz, Ellis (Cornell University, 197301)The problem of devising efficient algorithms for computing $Q(x_{1},\ldots,x_{r1},P(x_{1},\ldots,x_{r1}))$ where $P$ and $Q$ are multivariate polynomials is considered. It is shown that for polynomials which are completely ... 
The Symbolic Computation of Functions of Sequences over Finite Alphabets with Given Transition Probabilities by Sequence Length Independent Algorithms
Jackson, D.M.; Horowitz, Ellis (Cornell University, 197106)A special case of the problem discussed in this paper occurs in connection with nonstatistical classification and is introduced from this point of view. The special case concerns the computation of expectations of statistical ... 
A Unified View of the Complexity of Evaluation and Interpolation
Horowitz, Ellis (Cornell University, 197304)Four problems are considered: 1) from an nprecision integer compute its residues modulo n single precision primes; 2) from an ndegree polynomial compute its values at n points; 3) from n residues compute the unique ...