Now showing items 1-12 of 12

• #### Algorthms for Rational Function Arithmetic Operations ﻿

(Cornell University, 1971-11)
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 ﻿

(Cornell University, 1972-02)
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 ﻿

(Cornell University, 1971-06)
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 ﻿

(Cornell University, 1972-07)
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 0-1 unidimensional knapsack problem. ...
• #### The Efficient Calculation of Powers of Polynomials ﻿

(Cornell University, 1972-04)
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 ﻿

(Cornell University, 1971-12)
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 ﻿

(Cornell University, 1973-07)
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 ﻿

(Cornell University, 1971-09)
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 ﻿

(Cornell University, 1972-08)
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 ﻿

(Cornell University, 1973-01)
The problem of devising efficient algorithms for computing $Q(x_{1},\ldots,x_{r-1},P(x_{1},\ldots,x_{r-1}))$ 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 ﻿

(Cornell University, 1971-06)
A special case of the problem discussed in this paper occurs in connection with non-statistical 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 ﻿

(Cornell University, 1973-04)
Four problems are considered: 1) from an n-precision integer compute its residues modulo n single precision primes; 2) from an n-degree polynomial compute its values at n points; 3) from n residues compute the unique ...