Formally reviewed communication Irreducible polynomials and Barker sequences (2009)
Peter Borwein, Erich Kaltofen, Michael J. Mossinghoff
A Barker sequence is a finite sequence a0,..., an−1, each term ±1, for which every sum P i aiai+k with 0 < k < n is either 0, 1, or −1. It is widely conjectured that no Barker sequences of...
With an Additional Open Problem By (2009)
Erich Kaltofen, Robert M. Corless, J. Jeffrey, To Bobby, F. Caviness
on the occasion of his 60th birthday The success of the symbolic mathematical computation discipline is striking. The theoretical advances have been continuous and significant: Gröbner bases, the...
Expressing a Fraction of Two Determinants as a Determinant* ABSTRACT (2009)
Suppose the polynomials f and g in K[x1,..., xr] over the field K are determinants of non-singular m × m and n × n matrices, respectively, whose entries are in K ∪ {x1,..., xr}. Furthermore,...
Erich Kaltofen, Bin Li, Lihong Zhi, Zhengfeng Yang
We generalize the technique by Peyrl and Parillo [Proc. SNC 2007] to computing lower bound certificates for several well-known factorization problems in hybrid symbolicnumeric computation. The idea...
2.3 Gaussian Elimination Algorithm.......................... 7 (2009)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
Peter Borwein, Michael J. Mossinghoff, Erich Kaltofen
A Barker sequence is a finite sequence a0,..., an−1, each term ±1, for which every sum P i aiai+k with 0 < k < n is either 0, 1, or −1. It is widely conjectured that no Barker sequences of...
Lower bounds for approximate factorizations via (2008)
Erich Kaltofen, Bin Li, Kartik Sivaramakrishnan, Zhengfeng Yang, Lihong Zhi
semidefinite programming (extended abstract)*
ABSTRACT Polynomial Factorization: a Success Story ∗ [Plenary Lecture] † (2008)
The problem of factoring a polynomial in a single or several variables over a finite field, the rational numbers or the complex numbers is one of the success stories in the discipline of symbolic...
A probabilistic algorithm is developed for minimizing the number of black box probes in sparse multivariate interpolation. The Ben-Or/Tiwari interpolation [1, 4, 3] algorithm needs as input an upper...
Muhammad Mumtaz Ahmad, Gary L. Miller, Vijaya Ramach, Erich Kaltofen
Most of the fast algorithms now known seem to fall into a few general classes. The most common are ones based on repetition or iteration, classic examples being Euclid's algorithm for GCD,...
2.3 Gaussian Elimination Algorithm.......................... 7 (2008)
Angel D Az, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1
With an Additional Open Problem By (2008)
Erich Kaltofen, Robert M. Corless, David J. Jeffrey, To Bobby, F. Caviness
on the occasion of his 60th birthday The success of the symbolic mathematical computation discipline is striking. The theoretical advances have been continuous and significant: Gröbner bases, the...
Peter Borwein, Michael J. Mossinghoff, Erich Kaltofen
A Barker sequence is a finite sequence a0,..., an−1, each term ±1, for which every sum P i aiai+k with 0 < k < n is either 0, 1, or −1. It is widely conjectured that no Barker sequences of...
Erich Kaltofen, Gilles Villard
Computing the sign or the value of the determinant of an integer matrix, a complexity survey 1
Abstract: We show that over a field of characteristic p the solution to a non-singular system of n linear equations in n unknows, with 2 ≤ p < n, whose coefficient matrix is of displacement rank...
computational complexity ON THE COMPLEXITY OF COMPUTING DETERMINANTS (2008)
Erich Kaltofen, Gilles Villard
on the occasion of his 60th birthday Abstract. We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant,...
On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms (2008)
Erich Kaltofen, Zhengfeng Yang
Algebraic randomization techniques can be applied to hybrid symbolic-numeric algorithms. Here we consider the problem of interpolating a sparse rational function from noisy values. We develop a new...
Abstract Generic Gram-Schmidt Orthogonalization by Exact Division ∗ (2008)
Úlfar Erlingsson, Erich Kaltofen, David Musser
Given a vector space basis with integral domain coefficients, a variant of the Gram-Schmidt process produces an orthogonal basis using exact divisions, so that all arithmetic is within the integral...
We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse...
On the complexity of computing determinants (extended abstract (2008)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
Lower Bounds for Approximate Factorizations via Semidefinite Programming (extended abstract)* (2008)
Erich Kaltofen, Bin Li, Kartik Sivaramakrishnan, Zhengfeng Yang
The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations ∆f to the coefficients of the input polynomial f so that the deformed polynomial f +...
Algorithms and Problems (2008)
We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic...
Structured Low Rank Approximation of a Sylvester Matrix (2008)
D. Wang, L. Zhi, Erich Kaltofen, Zhengfeng Yang, Lihong Zhi
Abstract. The task of determining the approximate greatest common divisor (GCD) of univariate polynomials with inexact coefficients can be formulated as computing for a given Sylvester matrix a new...
H. Cohn, M. B. Nathanson, Erich Kaltofen, Noriko Yui
Motivated by a constructive realization of generalized dihedral groups as Galois groups over Q and by Atkin’s primality test, we present an explicit construction of the Hilbert class fields (ring...
DAGWOOD ASystem for Manipulating Polynomials Given byStraight-Line Programs* (2008)
Timothy S. Freeman, Gregory M. Imirzian, Erich Kaltofen, Lakshman Ya
Abstract. Wediscuss the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations. Our system is capable of...
Abstract Fast Polynomial Factorization Over High Algebraic Extensions of Finite Fields ∗ (2008)
New algorithms are presented for factoring polynomials of degree n over the finite field of q elements, where q is a power of a fixed prime number. When log q = n 1+a, where a> 0 is constant,...
Integral Polynomial Factorization * (2008)
An algorithm is presented which reduces the problem of finding the irreducible factors of a bivariate polynomial with integer coefficients in polynomial time in the total degree and the coefficient...
ABSTRACT On Exact and Approximate Interpolation of Sparse Rational Functions* (2008)
The black box algorithm for separating the numerator from the denominator of a multivariate rational function can be combined with sparse multivariate polynomial interpolation algorithms to...
We study the problem of bounding all factorizable polynomials away from a polynomial that is absolutely irreducible. Such separation bounds are useful for testing whether a numerical polynomial is...
Several standard problems in symbolic computation, such as greatest common divisor and factorization of polynomials, sparse interpolation, or computing solutions to overdetermined systems of...
Abstract FOXBOX: A System for Manipulating Symbolic Objects in Black Box Representation * (2008)
The FOXBOX system puts in practice the black box representation of symbolic objects and provides algorithms for performing the symbolic calculus with such representations. Black box objects are...
Expressing a Fraction of Two Determinants as a Determinant. (2008)
Koiran, Pascal, Kaltofen, Erich
Suppose the multivariate polynomials f and g are determinants of non-singular matrices A and B whose entries are variables or field elements. Furthermore, suppose that the quotient h = f/g is also a...
Expressing a Fraction of Two Determinants as a Determinant. (2008)
Koiran, Pascal, Kaltofen, Erich
Suppose the multivariate polynomials f and g are determinants of non-singular matrices A and B whose entries are variables or field elements. Furthermore, suppose that the quotient h = f/g is also a...
Approximate factorization of multivariate polynomials using singular value decomposition (2008)
Kaltofen, Erich, May, John P., Zhengfeng, Yang, Zhi, Lihong
We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain...
Angel Díaz, Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
This article, along with [Elkadi and Mourrain 1996], explain the correlation between residue theory and the Dixon matrix, which yields an alternative method for studying and approximating all common...
Unit Mixte, Erich Kaltofen, Gilles Villard Janvier
Computing the sign or the value of the determinant of an integer matrix, a complexity survey
On the complexity of computing determinants (Extended Abstract) (2007)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
We study the problem of bounding a polynomial away from polynomials which are absolutely irreducible. Such separation bounds are useful for testing whether a numerical polynomial is absolutely...
H. Cohn, M. B. Nathanson, Erich Kaltofen, Noriko Yui
Motivated by a constructive realization of generalized dihedral groups as Galois groups over Q and by Atkin’s primality test, we present an explicit construction of the Hilbert class fields (ring...
With an Additional Open Problem By (2007)
Erich Kaltofen, Robert M. Corless, David J. Jeffrey
The success of the symbolic mathematical computation discipline is striking. The theoretical
n algorithm is presented which reduces the probm lem of finding the irreducible factors of a bivariate polynoial with integer coefficients in polynomial time in the total i degree and the coefficient...
Parallel Algebraic Algorithm Design* Lecture Notes for a Tutorial (2007)
The notes following this introduction were written by students taking my graduate course 66.696 Parallel Algorithm Design, which I taught in the Fall of 1988. The material is largely based on the...
n this paper we prove by entirely elementary means a very effective version of the Hilbert Irreducibility n Theorem. We then apply our theorem to construct a probabilistic irreducibility test for...
FOXBOX: A System for Manipulating Symbolic Objects in Black Box Representation (2007)
The FOXBOX system puts in practice the black box representation of symbolic objects and provides algorithms for performing the symbolic calculus with such representations. Black box objects are...
Ulfar Erlingsson, Erich Kaltofen, David Musser
Given a vector space basis with integral domain coefficients, a variant of the Gram-Schmidt process produces an orthogonal basis using exact divisions, so that all arithmetic is within the integral...
Ioannis Z. Emiris, Erich Kaltofen, Victor Y. Pan
1 Supported by NSF grant No. CCR-9319776 and by GTE under a Graduate Computer Science Fellowship. 2 Supported by the European Union under ESPRIT FRISCO project LTR 21.024. 3 Supported by NSF grant...
Erich Kaltofen, Michael Mclean, Larry Norris, Dmitriy Morozov, John May, William Turner
We present an overview of the Maple Homework Assessment and Tutorial System developed in the Department of Mathematics at North Carolina State University. We have developed a suite of programs that...
H. Cohn, M. B. Nathanson, Erich Kaltofen, Noriko Yui
Motivated by a constructive realization of generalized dihedral groups as Galois groups over Q and by Atkin’s primality test, we present an explicit construction of the Hilbert class fields (ring...
A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of...
On the complexity of computing determinants (extended abstract (2007)
Erich Kaltofen, Gilles Villard
The computation of the determinant of an n × n matrix A of numbers or polynomials is a challenge for both numerical and symbolic methods. Numerical methods, such as Clarkson’s algorithm [10, 7]...
ABSTRACT Polynomial Factorization: a Success Story ∗ [Plenary Lecture] † (2007)
The problem of factoring a polynomial in a single or several variables over a finite field, the rational numbers or the complex numbers is one of the success stories in the discipline of symbolic...
We consider the problem of computing minimal real or complex deformations to the coefficients in a list of relatively prime real or complex multivariate polynomials such that the deformed polynomials...
06271 Executive Summary - Challenges in Symbolic Computation Software (2006)
Decker, Wolfram, Dewar, Mike, Kaltofen, Erich, Watt, Stephen M.
Symbolic computation software allows mathematicians, scientists, engineers, or educators to deal with elaborate calculations using a computer. The applications range from introducing the experimental...
06271 Abstracts Collection -- Challenges in Symbolic Computation Software (2006)
Decker, Wolfram, Dewar, Mike, Kaltofen, Erich, Watt, Stephen M.
From 02.07.06 to 07.07.06, the Dagstuhl Seminar 06271 ``Challenges in Symbolic Computation Software'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...
Generic matrix multiplication and memory management in linbox (2005)
We describe the design and implementation of two components in the LinBox library. The first is an implementation of black box matrix multiplication as a lazy matrixtimes-matrix product. The...
Generic matrix multiplication and memory management in linbox (2005)
We describe the design and implementation of two components in the LinBox library. The first is an implementation of black box matrix multiplication as a lazy matrixtimes-matrix product. The...
Approximate factorization of multivariate polynomials via differential equations (2004)
Shuhong Gao, Erich Kaltofen, John May
The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C....
Approximate factorization of multivariate polynomials via differential equations (2004)
Shuhong Gao, Erich Kaltofen, John May, Zhengfeng Yang, Lihong Zhi
The input to our algorithm is a multivariate polynomial, whose complex rational coecients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. We...
Approximate factorization of multivariate polynomials via differential equations (2004)
Shuhong Gao, Erich Kaltofen, John May
The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C....
Approximate factorization of multivariate polynomials via differential equations (2004)
Shuhong Gao, Erich Kaltofen, John May
The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C....
On the complexity of computing determinants. (2003)
Kaltofen, Erich, Villard, Gilles
(eng) By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann approach and...
Grabmeier, Johannes, Kaltofen, Erich
Incluye bibliografía e índice
On The Complexity Of Computing Determinants (2003)
Unit Mixte, Erich Kaltofen, Erich Kaltofen, ...
By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann...
LinBox: A Generic Library for Exact Linear Algebra. (2002)
Dumas, J.G., Gautier, T., Giesbrecht, M., Giorgi, Pascal, Hovinen, B., ...
(eng) LinBox is a high-performance generic software library for black box linear algebra over symbolic (exact) entry domains. The generic software methodology enables the user to instantiate the...
Computing the sign or the value of the determinant. (2002)
Kaltofen, Erich, Villard, Gilles
(eng) Computation of the sign of the determinant of a matrix and determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these...
An Attributed LL(1) Compilation of PASCAL into the Lambda-Calculus. (2002)
Kaltofen, Erich, Abdali, S. Kamal
A Pascal compiler is described whose target language is the lambda-calculus instead of some machine code. Although the lambda-calculus code generated by this complier can be executed by means of a...
Mark Giesbrecht, Erich Kaltofen, Wen-shin Lee
Let f(x1,..., xn) ∈ D[x1,..., xn] be a multivariate polynomial whose coefficients are in an integral domain D. A sparsest shift is a vector (s1,..., sn) ∈ K, where K is the field generated by the...
Li Chen, Wayne Eberly, Erich Kaltofen, B. David, Saunders William, J. Turner, ...
The main idea of the “black box ” approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain the...
Mark Giesbrecht, Erich Kaltofen, Wen-shin Lee
Let f(x1,...,xn) ∈ D[x1,...,xn] be a multivariate polynomial whose coefficients are in an integral domain D. A sparsest shift is a vector (s1,...,sn) ∈ K, whereK is the field generated by the...
Mark Giesbrecht, Erich Kaltofen, Wen-shin Lee
Let f(x1,..., xn) ∈ D[x1,..., xn] be a multivariate polynomial whose coefficients are in an integral domain D. A sparsest shift is a vector (s1,..., sn) ∈ K, where K is the field generated by the...
William Jonathan, Black Box, Linear Algebra, Linbox Library, William J. Turner, Erich Kaltofen, ...
(Under the direction of Erich Kaltofen.) Black box algorithms for exact linear algebra view a matrix as a linear operator on a vector space, gathering information about the matrix only though...
Efficient Matrix Preconditioners for Black Box Linear Algebra. (2001)
Chen, L., Eberly, W., Kaltofen, Erich, Saunders, B.D., Turner, W.J., ...
(eng) The main idea of the ``black box'' approach in exact linear algebra is to reduce matrix problems to the computation of minimum polynomials. In most cases preconditioning is necessary to obtain...
On the complexity of computing determinants (2001)
Erich Kaltofen, Gilles Villard
Abstract. We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius...
On The Complexity Of Computing (2001)
Erich Kaltofen, Gilles Villard
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal...
Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel’s algorithm (2000)
Erich Kaltofen, Wen-shin Lee, Austin A. Lobo
Interpolation algorithms whose computational complexities are sensitive to the sparsity of their target polynomials are one of the major contributions of computer algebra to computer science and...
Manfred Minimair, Hoon Hong, Erich Kaltofen, Dinesh Manocha, Michael Singer
The objective of this research has been to develop methods for computing resultants of composed polynomials, efficiently, by utilizing their composition structure. By the resultant of several...
On the Genericity of the Modular Polynomial GCD Algorithm (1999)
Erich Kaltofen, Michael Monagan
In this paper we study the generic setting of the modular GCD algorithm. We develop the algorithm for multivariate polynomials over Euclidean domains which have a special kind of remainder function....
Publications by Erich Kaltofen (1999)
Introduction to My Online Bibliography In the following the BASE URL for the online document is http://www.math.ncsu.edu/~kaltofen/ bibliography. Many of my publications are accessible through links...
Symbolic Computation in Java: an Appraisement (1999)
Laurent Bernardin, Bruce Char, Erich Kaltofen
Windowing Toolkit and the Swing components from the Java Foundation Classes. Internet browsers contain Java virtual machines for interpreting byte code of Java programs that are embedded into...
Challenges of Symbolic Computation - My Favorite Open Problems (1999)
Erich Kaltofen, Robert M. Corless, David J. Jeffrey
this paper, R. Corless and D. Jeffrey state an additional open problem, which was presented by Corless in his lecture at Fifth East Coast Computer Algebra Day in April 1998. A Brief History of...
Markus A. Hitz, Erich Kaltofen, Lakshman Y. N.
this paper is very special: nearness is measured coefficient-wise, i.e., in infinity norm. And the root locus is parametric, namely, the real axis. All previous solutions seem to have required that...
On the genericity of the modular polynomial GCD algorithm (1999)
In this paper we study the generic setting of the modular GCD algorithm. We develop the algorithm for multivariate polynomials over Euclidean domains which have a special kind of remainder function....
• Subresultants; fundamental theorem (without proof) [von zur Gathen and Gerhard
Subquadratic-time factoring of polynomials over finite fields (1998)
Abstract. New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant...
Efficient algorithms for computing the nearest polynomial with constrained roots (1998)
Markus A. Hitz, Erich Kaltofen
Continuous changes of the coefficients of a polynomial move the roots continuously. We consider the problem finding the minimal perturbations to the coefficients to move a root to a given locus, such...
Challenges of Symbolic Computation - My Favorite Open Problems (1998)
Erich Kaltofen, Robert M. Corless, J. Jeffrey, To Bobby, F. Caviness
The success of the symbolic mathematical computation discipline is striking. The theoretical advances have been continuous and significant: Grobner bases, the Risch integration algorithm, integer...
Markus A. Hitz, Erich Kaltofen, Lakshman Y. N
this paper is very special: nearness is measured coefficient-wise, i.e., in infinity norm. And the root locus is parametric, namely, the real axis. All previous solutions seem to have required that...
Subquadratic-time factoring of polynomials over finite fields (1998)
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time...
On randomized Lanczos algorithms (1997)
Las Vegas algorithms that are based on Lanczos's method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has...
On randomized Lanczos algorithms (1997)
Las Vegas algorithms that are based on Lanczos's method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has...
Fast polynomial factorization over high algebraic extensions of finite fields (1997)
New algorithms are presented for factoring polynomials of degree n over the finite field of q elements, where q is a power of a fixed prime number. When log q = n
Teaching computational abstract algebra (1997)
We report on the contents and pedagogy of a course in abstract algebra that was taught with the aid of educational software developed within the Mathematica system. We describe the topics covered and...
On randomized Lanczos algorithms (1997)
Las Vegas algorithms that are based on Lanczos's method for solving symmetric linear systems are presented and analyzed. These are compared to a similar randomized Lanczos algorithm that has...
Teaching computational abstract algebra (1997)
We report on the contents and pedagogy of a course in abstract algebra that was taught with the aid of educational software developed within the Mathematica system. We describe the topics covered and...
Angel Díaz, Erich Kaltofen, Victor Pan
this article we shall focus on the applications of the known fast methods to problems in science and engineering. For a more extensive set of references, please refer to Kaltofen's survey...
The Kharitonov theorem and its applications in symbolic mathematical computation (1997)
Markus A. Hitz, Erich Kaltofen
this paper we deal with the problem of diagnosing if a polynomial has such behaviour. In the past, various results deriving bounds of root displacement of a complex polynomial from the size of...
Fast Polynomial Factorization Over High Algebraic Extensions of Finite Fields (1997)
New algorithms are presented for factoring polynomials of degree n over the finite field of q elements, where q is a power of 2. When log q = n 1+a , where a ? 0 is constant, these algorithms are...
The Kharitonov theorem and its applications in symbolic mathematical computation † (1997)
Markus A. Hitz, Erich Kaltofen
The Kharitonov theorem provides a means of performing sensitivity analysis for the complex roots of polynomials whose coefficients (in power base) are perturbed. In particular, it gives a...
Teaching computational abstract algebra (1997)
We report on the contents and pedagogy of a course in abstract algebra that was taught with the aid of educational software developed within the Mathematica system. We describe the topics covered and...
Blocked Iterative Sparse Linear System Solvers for Finite Fields (1996)
The problem of solving a large sparse or structured system of linear equations in the symbolic context, for instance when the coefficients lie in a finite field, has arisen in several applications. A...
Integer division in residue number systems (1995)
Markus A. Hitz, Erich Kaltofen
Abstract--- This contribution to the ongoing discussion of division algorithms for residue number systems (RNS) is based on Newton iteration for computing the reciprocal. An extended RNS with twice...
Subquadratic-Time Factoring of Polynomials over Finite Fields (1995)
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time...
Integer Division in Residue Number Systems (1995)
Markus A. Hitz, Erich Kaltofen
This contribution to the ongoing discussion of division algorithms for residue number systems (RNS) is based on Newton iteration for computing the reciprocal. An extended RNS with twice the number of...
Subquadratic-Time Factoring of Polynomials over Finite Fields (1995)
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time...
Prediction Based Task Scheduling in Distributed Computing (1995)
Mehrdad Samadani, Erich Kaltofen
Introduction The effectiveness of task scheduling in a distributed environment is critically dependent on the timely identification of the least loaded nodes. Whether the issue of interest is...
Subquadratic-Time Factoring of Polynomials over Finite Fields (1995)
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time...
Subquadratic-Time Factoring of Polynomials over Finite Fields (1995)
New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time...
: We show that over a field of characteristic p the solution to a non-singular system of n linear equations in n unknows, with 2 p ! n, whose coefficient matrix is of displacement rank ff and which...
On Fast Multiplication of Polynomials Over Arbitrary Algebras (1991)
David G. Cantor, Erich Kaltofen
this paper we generalize the well-known Schonhage-Strassen algorithm for multiplying large integers to an algorithm for multiplying polynomials with coefficients from an arbitrary, not necessarily...
On fast multiplication of polynomials over arbitrary algebras (1991)
David G. Cantor, Erich Kaltofen
1. Introduction. In this paper we generalize the well-known Schönhage-Strassen algorithm for multiplying large integers to an algorithm for multiplying polynomials with coefficients from an...
Parallel algorithms for matrix normal forms. Linear Algebra and its Applications (1990)
Erich Kaltofen, M. S. Krishnamoorthy, B. David Saunders
Here we offer a new randomized parallel algorithm that determines the Smith normal form of a matrix with entries being univariate polynomials with coefficients in an arbitrary field. The algorithm...
Modular Rational Sparse Multivariate Polynomial Interpolation (1990)
Erich Kaltofen, Lakshman Y. N, John-michael Wiley
The problem of interpolating multivariate polynomials whose coefficient domain is the rational numbers is considered. The effect of intermediate number growth on a speeded Ben-Or and Tiwari algorithm...
Modular Rational Sparse Multivariate Polynomial Interpolation (1990)
Erich Kaltofen, Lakshman Y. N, John-michael Wiley
The problem of interpolating multivariate polynomials whose coefficient domain is the rational numbers is considered. The effect of intermediate number growth on a speeded Ben-Or and Tiwari algorithm...
An improved Las Vegas primality test (1989)
Erich Kaltofen, Thomas Valente, Noriko Yui
ABSTRACT: We present a modification of the Goldwasser-Kilian-Atkin primality test, which, when given an input n, outputs either prime or composite, along with a certificate of correctness which may...
Factorization of Polynomials Given by Straight-Line Programs (1989)
An algorithm is developed for the factorization of a multivariate polynomial represented by traight-line program into its irreducible factors. The algorithm is in random polynomial-time as a function...
Computing Greatest Common Divisors and Factorizations in Quadratic Number Fields (1989)
Erich Kaltofen, Heinrich Rolletschek
. In a quadratic number field Q( Ö" D ), D a squarefree integer, with class number 1 any algebraic integer can be decomposed uniquely into primes but for only 21 domains Euclidean algorithms...
Factorization of polynomials given by straight-line programs (1989)
An algorithm is developed for the factorization of a multivariate polynomial represented by a straight-line program into its irreducible factors. The algorithm is in random polynomial-time as a...
An improved Las Vegas primality test (1989)
Erich Kaltofen, Thomas Valente
ABSTRACT: We present a modification of the Goldwasser-Kilian-Atkin primality test, which, when given an input n, outputs either prime or composite, along with a certificate of correctness which may...
Computing greatest common divisors and factorizations in quadratic number fields (1989)
Erich Kaltofen, Heinrich Rolletschek
Abstract. Inaquadratic number field Q(√ ⎺ ⎺D), D asquarefree integer, with class number 1 any algebraic integer can be decomposed uniquely into primes but for only 21 domains Euclidean...
Efficient parallel evaluation of straight-line code and arithmetic circuits (1988)
Gary L. Miller, Vijaya Ramachandran, Erich Kaltofen
A new parallel algorithm is given to evaluate a straight line program. The algorithm evaluates a program over a commutative semi-ring R of degree d and size n in time O(log n(log nd)) using M(n)...
DAGWOOD - A System for Manipulating Polynomial Given by Straight-Line Programs (1988)
Timothy S. Freeman, Gregory M. Imirzian, Erich Kaltofen, Lakshman Yagati
. We discuss the design, implementation, and benchmarking of a system tha an manipulate symbolic expressions represented by their straight-line computations. Our syst c tem is capable of performing...
Improved Sparse Multivariate Polynomial Interpolation Algorithms* (1988)
Erich Kaltofen, Lakshman Yagati
. We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the other due...
Greatest Common Divisors of Polynomials Given by Straight-Line Programs (1988)
. F Algorithms on multivariate polynomials represented by straight-line programs are developed irst it is shown that most algebraic algorithms can be probabilistically applied to data that is given...
Improved Sparse Multivariate Polynomial Interpolation Algorithms (1988)
Erich Kaltofen, Lakshman Yagati
. We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the other due...
Efficient parallel evaluation of straight-line code and arithmetic circuits (1988)
Gary L. Miller, Erich Kaltofen
Abstract. A new parallel algorithm is given to evaluate a straight-line program. The algorithm evaluates a program over a commutative semi-ring R of degree d and size n in time O((Iog n)(log nd))...
Improved Sparse Multivariate Polynomial Interpolation Algorithms (1988)
Erich Kaltofen, Lakshman Yagati
Abstract. We consider the problem of interpolating sparse multivariate polynomials from their values. We discuss two algorithms for sparse interpolation, one due to Ben-Or and Tiwari (1988) and the...
Greatest common divisors of polynomials given by straight-line programs (1988)
Algorithms on multivariate polynomials represented by straight-line programs are developed. First it is shown that most algebraic algorithms can be probabilistically applied to data that is given bya...
Greatest common divisors of polynomials given by straight-line programs (1988)
Abstract. Algorithms on multivariate polynomials represented by straight-line programs are developed. First, it is shown that most algebraic algorithms can be probabilistically applied to data that...
Fast parallel computation of Hermite and Smith forms of polynomial matrices (1987)
Erich Kaltofen, M. S. Krishnamoorthy, B. David Saunders
Abstract. Boolean circuits of polynomial size and poly-logarithmic depth are given for computing the Hermite and Smith normal forms of polynomial matrices over finite fields and the field of rational...
Deterministic Irreducibility Testing of Polynomials over Large Finite Fields (1987)
We present a sequential deterministic polynomial-time algorithm for testing dense multivariate polynomials over a large finite field for irreducibility. All previously known algorithms were of a...
hree theorems are presented that establish polynomial straight-line complexity for cer- . T tain operations on polynomials given by straight-line programs of unbounded input degree he first theorem...
Three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given by straight-line programs of unbounded input degree. The first theorem...
Fast parallel absolute irreducibility testing (1985)
e present a fast parallel deterministic algorithm for testing multivariate integral polyno-c mials for absolute irreducibility, that is irreducibility over the complex numbers. More pre isely, we...
Fast parallel absolute irreducibility testing (1985)
We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we...
Anew algorithm is introduced which computes the multivariate leading coefficients of polynomial factors from their univariate images. This algorithm is incorporated into a sparse Hensel lifting...
Anew algorithm is introduced which computes the multivariate leading coefficients of polynomial factors from their univariate images. This algorithm is incorporated into a sparse Hensel lifting...
Consider a polynomial f with an arbitrary but fixed number of variables and with integral coefficients. We present an algorithm which reduces the problem of finding the irreducible factors of f in...
Motivated by a constructive realization of dihedral groups of prime degree as Galois group over the field of rational numbers, we give an explicit construction of the Hilbert class fields of some...
On the Complexity of Finding Short Vector in Integer Lattices (1983)
this paper we present a modified version of this algorithm n
Early Termination in Ben-Or/Tiwari Sparse Interpolation and a Hybrid of Zippel's Algorithm
Erich Kaltofen, Wen-shin Lee, Austin A. Lobo
this paper we revisit the original two algorithms. Zippel's algorithm has a shortcoming over Ben-Or's and Tiwari's in that it proceeds one variable at a time, and each new variable is...
On the Genericity of the Modular Polynomial GCD Algorithm*
Erich Kaltofen North, Erich Kaltofen, Michael Monagan
In this paper we study the generic setting of the modular GCD algorithm. We develop the algorithm for multivariate polynomials over Euclidean domains which have a special kind of remainder function....
A Note on the Risch Differential Equation
This paper relates to the technique of integrating a function in a purely transcendental regular elementary Liouville extension by prescribing degree bounds for the transcendentals and then solving...
Symbolic Computation in Java: an Appraisement
Laurent Bernardin Bruce, Erich Kaltofen
Windowing Toolkit and the Swing components from the Java Foundation Classes. Internet browsers contain Java virtual machines for interpreting byte code of Java programs that are embedded into...
Generic Gram-Schmidt Orthogonalization by Exact Division
Ulfar Erlingsson, Erich Kaltofen, David Musser
Given a vector space basis with integral domain coefficients, a variant of the Gram-Schmidt process produces an orthogonal basis using exact divisions, so that all arithmetic is within the integral...
Symbolic Computation in Java: an Appraisement
Laurent Bernardin, Erich Kaltofen
Windowing Toolkit and the Swing components from the Java Foundation Classes. Internet browsers contain Java virtual machines for interpreting byte code of Java programs that are embedded into...