Throughout my career, I had the good fortune to meet people and see ideas which have greatly influenced my scientific thinking. In the following I would like to tell my story of some.

In [IEEE Trans. Information Theory, vol. 67, nr. 1 (2021)] we have presented error-correcting algorithms that interpolate sparse univariate polynomials from values at arguments which the algorithms compute. We have assumed that the input polynomials are sparse in terms that are powers of the variable (standard basis) or sparse in Chebyshev basis polynomials. We recover all polynomials of sparsity ≤ B that from our N input points interpolate at least N − E of the points, that is, correct ≤ E errors in the values at the error capacity E/N. Our IEEE Transactions algorithms have, roughly, an error capacity of 0.75/B for power basis and 0.66/B for Chebyshev basis.

The proof-of-work interactive protocol by Shafi Goldwasser, Yael T. Kalai and Guy N. Rothblum (GKR) [STOC 2008, JACM 2015] certifies the execution of an algorithm via the evaluation of a corresponding boolean or arithmetic circuit whose structure is known to the verifier by circuit wiring algorithms that define the uniformity of the circuit. Here we study protocols whose prover time- and space-complexities are within a poly-logarithmic factor of the time- and space-complexity of the algorithm; we call those protocols 'prover-nearly-optimal.' We show that the uniformity assumptions can be relaxed from LOGSPACE to polynomial-time in the bit-lengths of the labels which enumerate the nodes in the circuit. Our protocol applies GKR recursively to the arising sumcheck problems on each level of the circuit whose values are verified, and deploys any of the prover-nearly-optimal versions of GKR on the constructed sorting/prefix circuits with log-depth wiring functions.

We present Hermite polynomial interpolation algorithms that for a sparse univariate polynomial f with coefficients from a field compute the polynomial from fewer points than the classical algorithms. If the interpolating polynomial f has t terms, our algorithms, which use randomization, require argument/value triples (wi,f(wi),f'(wi)) for i=0, ..., t + ↾(t+1)/2↿ - 1, where w is randomly sampled and the probability of a correct output is determined from a degree bound for f. With f' we denote the derivative of f. Our algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases. We have algorithms that can correct errors in the points by oversampling at a limited number of good values. If an upper bound B ≥ t for the number of terms is given, our algorithms use a randomly selected w and, with high probability, t/2 + B triples, but then never return an incorrect output.

In https://arxiv.org/abs/1609.00840 (see also https://doi.org/10.1007/s11425-018-1594-2), Dongming Wang and Jing Yang in 2016 have posed the problem how to compute the "third'' discriminant of a polynomial f(x) = (x-α1)…(x-αn), δ3(f) = Π ((αi+αj-αk-αℓ) (αi-αj+αk-αℓ)(αi-αj-αk+αℓ))1≤<j<k<ℓ≤n from the coefficients of f; note that δ3 is a symmetric polynomial in the αi. For complex roots, δ3(f) = 0 if the mid-point (average) of $2$ roots is equal the mid-point of another 2 roots. Iterated resultant computations yield the square of the third discriminant. We apply a symbolic homotopy by Kaltofen and Trager [JSC, vol. 9, nr. 3, pp. 301--320 (1990)] to compute its squareroot. Our algorithm uses polynomially many coefficient field operations in the degree of f.

Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or ≥ 𝓁 +1, where 𝓁 is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic 𝓁+1, the minimum number of values for interpolating a polynomial of degree ≤ D is D+1+2E(𝓁+1) when ≤ E of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that requires fewer values, that is, that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or ≥ D+1. Our algorithm requires (𝓁+1)D + 1 - (𝓁+1)𝓁/2 + 2E values.

We present sparse interpolation algorithms for recovering a polynomial with ≤ B terms from N evaluations at distinct values for the variable when ≤ E of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars K and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of K is ≠ 2. Our algorithms return a list of valid sparse interpolants for the N support points and run in polynomial-time. For standard power basis our algorithms sample at N = ⌊4/3 E + 2⌋B points, which are fewer points than N = 2(E + 1)B - 1 given by Kaltofen and Pernet in 2014. For Chebyshev basis our algorithms sample at N = ⌊3/2E + 2⌋B points, which are also fewer than the number of points required by the algorithm given by Arnold and Kaltofen in 2015, which has N = 74⌊E/13 +1⌋ for B = 3 and E ≥ 222. Our method shows how to correct 2 errors in a block of 4B points for standard basis and how to correct 1 error in a block of 3B points for Chebyshev Basis.

An algorithm for interpolating a polynomial f from evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a sum of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients is given by Lakshman Y. N. and Saunders [SIAM J. Comput., vol. 24, nr. 2 (1995)]; Kaltofen and Lee [JSC, vol. 36, nr. 3--4 (2003)] analyze a randomized early termination version which computes the sparsity t. Those algorithms mirror Prony's algorithm for the standard power basis to the Chebyshev Basis of the First Kind. An alternate algorithm by Arnold's and Kaltofen's [Proc. ISSAC 2015, Sec. 4] uses Prony's original algorithm for standard power terms. Here we give sparse interpolation algorithms for generalized Chebyshev polynomials, which include the Chebyshev Bases of the Second, Third and Fourth Kind. Our algorithms also reduce to Prony's algorithm. If given on input a bound B >= t for the sparsity, our new algorithms deterministically recover the sparse representation in the First, Second, Third and Fourth Kind Chebyshev representation from exactly t + B evaluations. Finally, we generalize our algorithms to bases whose Chebyshev recurrences have parametric scalars. We also show how to compute those parameter values which optimize the sparsity of the representation in the corresponding basis, similar to computing a sparsest shift.

We present an interactive probabilistic proof protocol that certifies in (log N)O(1) arithmetic and Boolean operations for the verifier the determinant, for example, of an N x N matrix over a field whose entries a(i,j) are given by a single (log NO(1)-depth arithmetic circuit, which contains (log NO(1) field constants and which is polynomial time uniform, for example, which has size (log NO(1). The prover can produce the interactive certificate within a (log NO(1) factor of the cost of computing the determinant. Our protocol is a version of the proofs for muggles protocol by Goldwasser, Kalai and Rothblum [STOC 2008, J. ACM 2015]. An application is the following: suppose in a system of k homogeneous polynomials of total degree ≤ d in the k variables y1,...,yk the coefficient of the term y1e1 ... ykek in the i-th polynomial is the (hypergeometric) value ((i+e1 + ... + ek)!)/((i!)(e1!)...(ek!)), where e! is the factorial of e. Then we have a probabilistic protocol that certifies (projective) solvability or inconsistency of such a system in (k log(d))O(1) bit complexity for the verifier, that is, in polynomial time in the number of variables k and the logarithm of the total degree, log(d).

Consider solving a black box linear system, A(u) x = b(u), where the entries are polynomials in u over a field K, and A(u) is full rank. The solution, x = 1/g(u) f(u), where g is always the least common monic denominator, can be found by evaluating the system at distinct points ξl in K. The solution can be recovered even if some evaluations are erroneous. In [Boyer and Kaltofen, Proc. SNC 2014] the problem is solved with an algorithm that generalizes Welch/Berlekamp decoding of an algebraic Reed-Solomon code. Their algorithm requires the sum of a degree bound for the numerators plus a degree bound for the denominator of the solution. It is possible that the degree bounds input to their algorithm grossly overestimate the actual degrees. We describe an algorithm that given the same inputs uses possibly fewer evaluations to compute the solution. We introduce a second count for the number of evaluations required to recover the solution based on work by Stanley Cabay. The Cabay count includes bounds for the highest degree polynomial in the coefficient matrix and right side vector, but does not require solution degree bounds. Instead our algorithm iterates until the Cabay termination criterion is reached. At this point our algorithm returns the solution. Assuming we have the actual degrees for all necessary input parameters, we give the criterion that determines when the Cabay count is fewer than the generalized Welch/Berlekamp count.

Computational problem certificates are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.

Ankur Moitra in his paper at STOC 2015 has given an in-depth analysis of how oversampling improves the conditioning of the arising Prony systems for sparse interpolation and signal recovery from numeric data. Moitra assumes that oversampling is done for a number of samples beyond the actual sparsity of the polynomial/signal. We give an algorithm that can be used to compute the sparsity and estimate the minimal number of samples needed in numerical sparse interpolation. The early termination strategy of polynomial interpolation has been incorporated in the algorithm: by oversampling at a small number of extra sample points we can diagnose that the sparsity has not been reached.

We present an error-correcting interpolation algorithm for a univariate black-box polynomial that has a sparse representation using Chebyshev polynomials as a term basis. Our algorithm assumes that an upper bound on the number of erroneous evaluations is given as input, and is a generalization of the algorithm by Lakshman and Saunder [SIAM J. Comput., vol. 24 (1995)] for interpolating sparse Chebyshev polynomials and the techniques in error-correcting sparse interpolation in the usual basis of consecutive powers of the variable due to Comer, Kaltofen, and Pernet [Proc. ISSAC 2012 and 2014]. We prove the correctness of our list-decoder-based algorithm with a Descartes-rule-of-signs-like property for sparse polynomials in Chebyshev basis. We also give a new algorithm that reduces the sparse interpolation in Chebyshev basis to that in power basis, thus making the many techniques for the sparse interpolation in power basis, for instance, supersparse (lacunary) interpolation over large finite fields, available to interpolation in Chebyshev basis. Furthermore, we can customize the randomized early termination algorithms from Kaltofen and Lee [J. Symb. Comput., vol. 36 (2003)] to our new approach.

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size N, meaning N times a factor No(1), i.e., a factor Nη(N) with limN → ∞ η(N) = 0.

We present algorithms performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Based on the initial work by Comer, Kaltofen and Pernet [Proc. ISSAC 2012], we define the sparse polynomial interpolation codes and state that their minimal distance is precisely the code-word length divided by twice the sparsity. At ISSAC 2012, we have given a decoding algorithm for as much as half the minimal distance and a list decoding algorithm up to the minimal distance.

In [Kaltofen and Yang, Proc. ISSAC 2013] we have generalized algebraic error-correcting decoding to multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors ("outliers"). Here we present a different algorithm that can interpolate a sparse multivariate rational function from evaluations where the error rate is 1/q for any q > 2, which our ISSAC 2013 algorithm could not handle. When implemented as a numerical algorithm we can, for instance, reconstruct a fraction of trinomials of degree 15 in 50 variables with non-outlier evaluations of relative noise as large as 10-7 and where as much as 1/4 of the 14717 evaluations are outliers with relative error as small as 0.01 (large outliers are easily located by our method).

Error-correcting decoding is generalized to multivariate sparse rational function recovery from evaluations that can be numerically inaccurate and where several evaluations can have severe errors ("outliers"). The generalization of the Berlekamp-Welch decoder to exact Cauchy interpolation of univariate rational functions from values with faults is by Kaltofen and Pernet in 2012. We give a different univariate solution based on structured linear algebra that yields a stable decoder with floating point arithmetic. Our multivariate polynomial and rational function interpolation algorithm combines Zippel's symbolic sparse polynomial interpolation technique [Ph.D. Thesis MIT 1979] with the numeric algorithm by Kaltofen, Yang, and Zhi [Proc. SNC 2007], and removes outliers ("cleans up data") through techniques from error correcting codes. Our multivariate algorithm can build a sparse model from a number of evaluations that is linear in the sparsity of the model.

We analyze the Matrix Berlekamp/Massey algorithm, which generalizes the Berlekamp/Massey algorithm [Massey 1969] for computing linear generators of scalar sequences. The Matrix Berlekamp/Massey algorithm computes a minimal matrix generator of a linearly generated matrix sequence and has been first introduced by Rissanen [1972a], Dickinson et al. [1974], and Coppersmith [1994]. Our version of the algorithm makes no restrictions on the rank and dimensions of the matrix sequence. We also give new proofs of correctness and complexity for the algorithm, which is based on self-contained loop invariants and includes an explicit termination criterion for a given determinantal degree bound of the minimal matrix generator.

We propose algorithms performing sparse interpolation with errors, based on Prony's--Ben-Or's & Tiwari's algorithm, using a Berlekamp/Massey algorithm with early termination. First, we present an algorithm that can recover a t-sparse polynomial f from a sequence of values, where some of the values are wrong, spoiled by either random or misleading errors. Our algorithm requires bounds T ≥ t and E ≥ e, where e is the number of evaluation errors. It interpolates f(ωi) for i = 1,..., 2T(E + 1), where ω is a field element at which each non-zero term evaluates distinctly.

We deploy numerical semidefinite programming and conversion to exact rational inequalities to certify that for a positive semidefinite input polynomial or rational function, any representation as a fraction of sums-of-squares of polynomials with real coefficients must contain polynomials in the denominator of degree no less than a given input lower bound. By Artin's solution to Hilbert's 17th problems, such representations always exist for some denominator degree. Our certificates of infeasibility are based on the generalization of Farkas's Lemma to semidefinite programming.

We present a method for interpolating a supersparse blackbox rational function with rational coefficients, for example, a ratio of binomials or trinomials with very high degree. We input a blackbox rational function, as well as an upper bound on the number of non-zero terms and an upper bound on the degree. The result is found by interpolating the rational function modulo a small prime p, and then applying an effective version of Dirichlet's Theorem on primes in an arithmetic progression progressively lift the result to larger primes. Eventually we reach a prime number that is larger than the inputted degree bound and we can recover the original function exactly. In a variant, the initial prime p is large, but the exponents of the terms are known modulo larger and larger factors of p-1.

We present certificates for the positive semidefiniteness of an n by n matrix A, whose entries are integers of binary length log ||A||, that can be verified in O(n(2+µ) (log ||A||)(1+µ) binary operations for any µ > 0. The question arises in Hilbert/Artin-based rational sum-of-squares certificates (proofs) for polynomial inequalities with rational coefficients. We allow certificates that are validated by Monte Carlo randomized algorithms, as in Rusins Freivalds's famous 1979 quadratic time certification for the matrix product. Our certificates occupy O(n(3+µ) (log ||A||)(1+µ) bits, from which the verfication algorithm randomly samples a quadratic amount.

We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.

We give a stability criterion for real polynomial inequalities with floating point or inexact scalars by estimating from below or computing the radius of semidefiniteness. That radius is the maximum deformation of the polynomial coefficient vector measured in a weighted Euclidean vector norm within which the inequality remains true. A large radius means that the inequalities may be considered numerically valid.

Suppose the polynomials f and g in K[x1,...,xr] over the field K are determinants of non-singular m x m and n x n matrices, respectively, whose entries are in K ∪ x1,...,xr. Furthermore, suppose h = f/g is a polynomial in K[x1,..., xr]. We construct an s x s matrix C whose entries are in K ∪ x1,...,xr, such that h = det(C) and s = γ (m+n)6, where γ = O(1) if K is an infinite field or if for the finite field K = F{q} with q elements we have m = O(q), and where γ = (logq m)1+o(1) if q = o(m). Our construction utilizes the notion of skew circuits by Toda and WSK circuits by Malod and Portier. Our problem was motivated by resultant formulas derived from Chow forms.

We generalize the technique by Peyrl and Parillo [Proc. SNC 2007] to computing lower bound certificates for several well-known factorization problems in hybrid symbolic-numeric computation. The idea is to transform a numerical sum-of-squares (SOS) representation of a positive polynomial into an exact rational identity. Our algorithms successfully certify accurate rational lower bounds near the irrational global optima for benchmark approximate polynomial greatest common divisors and multivariate polynomial irreducibility radii from the literature, and factor coefficient bounds in the setting of a model problem by Rump (up to n = 14, factor degree = 13.

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 interpolate a sparse rational function. domization and early termination strategies are exploited to minimize the number of black box evaluations. In addition, rational number coefficients are recovered from modular images by rational vector recovery. The need for separate numerator and denominator size bounds is avoided via correction, and the modulus is minimized by use of lattice basis reduction, a process that can be applied to sparse rational function vector recovery itself. Finally, one can deploy sparse rational function interpolation algorithm in the hybrid symbolic-numeric setting when the black box for the function returns real and complex values with noise. We present and analyze five new algorithms for the above problems and demonstrate their effectiveness on a mark implementation.

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 polynomial-time in (l+d)n, where l is the size of the input polynomial. In supersparse polynomials, the term degrees enter logarithmically as their numbers of binary digits into the size measure l. The factors are again represented as supersparse polynomials. If the factors are represented as straight-line programs or black box polynomials, we can achieve randomized polynomial-time in (l+d)O(1). Our approach follows that by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over algebraic number fields. We generalize our ISSAC 2005 results for computing linear factors of supersparse bivariate polynomials over the rational numbers by appealing to recent lower bounds on the height of algebraic numbers and to a special case of the former Lang conjecture.

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 have a greatest common divisor (GCD) of at least a given degree k. In addition, we restrict the deformed coefficients by a given set of linear constraints, thus introducing the linearly constrained approximate GCD problem. We present an algorithm based on a version of the structured total least norm (STLN) method and demonstrate on a diverse set of benchmark polynomials that the algorithm in practice computes globally minimal approximations. As an application of the linearly constrained approximate GCD problem we present an STLN-based method that computes a real or complex polynomial the nearest real or complex polynomial that has a root of multiplicity at least k. We demonstrate that the algorithm in practice computes on the benchmark polynomials given in the literature the known globally optimal nearest singular polynomials. Our algorithms can handle, via randomized preconditioning, the difficult case when the nearest solution to a list of real input polynomials actually has non-real complex coefficients.

Several standard problems in symbolic computation, such as greatest common divisor and factorization of polynomials, sparse interpolation, or computing solutions to overdetermined systems of polynomial equations have non-trivial solutions only if the input coefficients satisfy certain algebraic constraints. Errors in the coefficients due to floating point round-off or through phsical measurement thus render the exact symbolic algorithms unusable. By symbolic-numeric methods one computes minimal deformations of the coefficients that yield non-trivial results. We will present hybrid algorithms and benchmark computations based on Gauss-Newton optimization, singular value decomposition(SVD) and structure-preserving total least squares (STLS) fitting for several of the above problems.A significant body of results to solve those "approximate computer algebra" problems has been discovered in the past 10 years. In the Computer Algebra Handbook the section on "Hybrid Methods" concludes as follows [2]: "The challenge of hybrid symbolic-numeric algorithms is to explore the effects of imprecision, discontinuity, and algorithmic complexity by applying mathematical optimization, perturbation theory, and inexact arithmetic and other tools in order to solve mathematical problems that today are not solvable by numerical or symbolic methods alone." The focus of our tutorial is on how to formulate several approximate symbolic computation problems as numerical problems in linear algebra and optimization and on software that realizes their solutions.Approximate Greatest Common Divisors [3]. Our paper at this conference presents a solution to the approximate GCD problem for several multivariate polynomials with real or complex coefficients. In addition, the coefficients of the minimally deformed input coefficients can be linearly constrained. In our tutorial we will give a precise definition of the approximate polynomial GCD problem and we will present techniques based on parametric optimization (slow) and STLS or Gauss/Newton iteration (fast) for its numerical solution. The fast methods can compute globally optimal solutions, but they cannot verify global optimality. We show how to apply the constrained approximate GCD problem to computing the nearest singular polynomial with a root of multiplicity at least k≥2.Approximate Factorization of Multivariate Polynomials [1]. Our solution and implementation of the approximate factorization problem follows our approach for the approximate GCD problem. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use SVD or STLS and Gauss/Newton optimization to numerically compute the approximate multivariate factors.Solutions of Zero-dimensional Polynomial Systems [4]. We translate a system of polynomials into a system of linear partial differential equations (PDEs) with constant coefficients. The PDEs are brought to an involutive form by symbolic prolongations and numeric projections via SVD. The solutions of the polynomial system are obtained by solving an eigen-problem constructed from the null spaces of the involutive system and its geometric projections.

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 polynomials, the term degrees can have hundreds of digits as binary numbers. Our algorithms are Monte Carlo randomized for quadratic factors and deterministic for linear factors. Our approach relies on the results by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over the rational numbers. Furthermore, we show that the problem of determining the irreducibility of a supersparse bivariate polynomial over a large finite field of any characteristic is co-NP-hard via randomized reductions.

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 matrix-times-matrix product. The implementation uses template meta-programming to set the intermediate vector type used during application of the matrix product. We also describe an interface mechanism that allows incorporation of external components with native memory management such as garbage collection into LinBox. An implementation of the interface based on SACLIB's field arithmetic procedures is presented.

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. We seek to perturb the coefficients by a small quantitity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known. We give a numerical multivariate greatest common divisor algorithm and use it on a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, even when the relative error in the input is substantial (10-3).

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 computation. In the early 1960s implementors investigated the constructive methods known from classical algebra books, but--with the exception of Gauss's distinct degree factorization algorithm--found the algorithms quite inefficient in practice [16]. The contributions in algorithmic techniques that have been made over the next 40 years are truly a hallmark of symbolic computation research.

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 irreducible, given a certain tolerance on its coefficients. Using an absolute irreducibility criterion due to Ruppert, we are able to find useful separation bounds, in several norms, for bivariate polynomials. We also use Ruppert's criterion to derive new, more effective Noether forms for polynomials of arbitrarily many variables. These forms lead to small separation bounds for polynomials of arbitrarily many variables.

As a sub-procedure our algorithm executes the Berlekamp/Massey algorithm on a sequence of large integers or polynomials. We give a fraction-free version of the Berlekamp/Massey algorithm, which does not require rational numbers or functions and GCD operations on the arising numerators and denominators. The relationship between the solution of Toeplitz systems, Padé approximations, and the Euclidean algorithm is classical. Fraction-free versions [3] can be obtained from the subresultant PRS algorithm [2]. Dornstetter [6] gives an interpretation of the Berlekamp/Massey algorithm as a partial extended Euclidean algorithm. We map the subresultant PRS algorithm onto Dornstetter's formulation. We note that the Berlekamp/Massey algorithm is more efficient than the classical extended Euclidean algorithm.

This paper provides an adaptive version of the unblocked baby steps/giant steps algorithm [20, Section 2]. The result is most easily stated when b |#| where # is the determinant to be computed and # with 1 is not known. Note that by Hadamard's bound |#|#n(b +log 2 (n)/2), so # = 0 covers the worst case. We describe a Monte Carlo algorithm that produces #in(n bit operations, again with standard matrix arithmetic. The corresponding bit complexity of the early termination Gaussian elimination method is 4-# , which is always more, and that of the algorithm by [10] is (n 1+1/2 Our adaptive determinant algorithm can be speeded by use of subcubic matrix multiplication algorithms so as to outperform an early termination Gaussian elimination algorithm that employs subcubic matrix multiplication. Such results seem, however, of purely theoretical interest; see Section 4 for a more in-depth discussion. Here we add that the exponent "+o(1)" in the version that uses cubic matrix multiplication and that has bit complexity (n is introduced (except when b n) because the moduli of the Chinese remainder algorithm cannot be chosen of fixed magnitude. However, for all practical purposes primes with 32 or 64 bit will su#ce to recover determinants of any reasonable length, say of fewer 10 binary digits. Therefore the polylogarithmic factors in our complexity estimates do not degrade the practical performance of our method

Article Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm Share on Authors: Erich Kaltofen Department of Mathematics, North Carolina State University, Raleigh, North Carolina Department of Mathematics, North Carolina State University, Raleigh, North CarolinaView Profile , Wen-shin Lee Department of Mathematics, North Carolina State University, Raleigh, North Carolina Department of Mathematics, North Carolina State University, Raleigh, North CarolinaView Profile , Austin A. Lobo Dept. of Mathematics and Computer Science, Washington College, Chestertown, Maryland Dept. of Mathematics and Computer Science, Washington College, Chestertown, MarylandView Profile Authors Info & Claims ISSAC '00: Proceedings of the 2000 international symposium on Symbolic and algebraic computationJuly 2000 Pages 192–201https://doi.org/10.1145/345542.345629Online:01 July 2000Publication History 22citation308DownloadsMetricsTotal Citations22Total Downloads308Last 12 Months14Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Symbolic computation in Java: an appraisement Authors: Laurent Bernardin Institut für Wissenschaftliches Rechnen, Eidgenössische Technische Hochschule, Zurich, Switzerland Institut für Wissenschaftliches Rechnen, Eidgenössische Technische Hochschule, Zurich, SwitzerlandView Profile , Bruce Char Department of Mathematics and Computer Science, Drexel University, Philadelphia, Pennsylvania Department of Mathematics and Computer Science, Drexel University, Philadelphia, PennsylvaniaView Profile , Erich Kaltofen Department of Mathematics, North Carolina State University, Raleigh, North Carolina Department of Mathematics, North Carolina State University, Raleigh, North CarolinaView Profile Authors Info & Claims ISSAC '99: Proceedings of the 1999 international symposium on Symbolic and algebraic computationJuly 1999 Pages 237–244https://doi.org/10.1145/309831.309946Published:01 July 1999Publication History 14citation450DownloadsMetricsTotal Citations14Total Downloads450Last 12 Months23Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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 for parametric root locations the distance expression is at least differentiable: they and we have proven results using the Euclidean distance. Infinity norm leads us [7] to linear programming problems, whose parametric versions we do not know how to solve efficiently. We can solve our specific problem efficiently, that is in polynomial-time in the degree and input length, because an explicit expression for the distance to the nearest polynomial with a real root can be derived from a result in [17], or alternatively by eigenvalue analysis of companion matrices in [15, Section 4.2]. The expression involves absolute values, but by a stroke of luck can be minimized over the entire real axis.

In this paper we st,udy the generic setting of the modular GCD algorithm.We develop the algorithm for multivariate polynomials over Euclidean domains which have a spc:&l kind of remainder function.Details for the parameterixation and generic Maple code are given.Applying this grncric algorithm to a GCD problem in Z/(~) [t][z] where 1~ is small yields an improved asymptotic performance over t.he usual approach, and a very practical algorithm for polynomials over small finite fields.

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 stored as functions.For instance: a black box polynomial is a procedure that takes values for the variables as input and evaluates the polynomial at that given point.FOXBOX can compute the greatest common divisor and factorize polynomials in black box representation, producing as output new black boxes.It also can compute the standard sparse distributed representation of a black box polynomial, for example, one which was computed for an irreducible factor.We establish that the black box representation of objects can push the size of symbolic expressions far beyond what standard data structures could handle before.Furthermore, FOXBOX demonstrates the generic program design methodology.The FOXBOX system is written in C++.C++ template arguments provide for abstract domain types.Currently, FOXBOX can be compiled with SACLIB 1.1, Gnu-MP 1.0, and NTL 2.0 as its underlying field and polynomial arithmetic.Multiple arithmetic plugins can be used in the same computation.FOXBOX provides an MPI-compliant distribution mechanism that allows for parallel and distributed execution of FOXBOX programs.Finally, FOXBOX plugs into a server/client-style Maple application interface.

Continuous changes of the coecients of a polynomial move the roots continuously.We consider the problem nding the minimal perturbations to the coecients to move a root to a given locus, such as a single point, the real or imaginary axis, the unit circle, or the right half plane.We measure minimality in both the Euclidean distance to the coecient vector and maximal coecient-wise change in absolute value (in nity norm), either with entirely real or with complex coecients.If the locus is a piecewise parametric curve, we can give ecient, i.e., polynomial time algorithms for the Euclidean norm; for the in nity norm we present an ecient algorithm when a root of the minimally perturbed polynomial is constrained to a single point.In terms of robust control, we are able to compute the radius of stability i n t h e Euclidean norm for a wide range of convex open domains of the complex plane.

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 been used for integer factorization, and to the (provably reliable) algorithm of Wiedemann. The analysis suggests that our Lanczos algorithms are preferable to several versions of Wiedemann's method for computations over large fields, especially for certain symmetric matrix computations. 1 Introduction Sparse or structured systems of linear equations over fields arise in a variety of applications; for example, many methods for integer factorization require the solutions of large, sparse systems over finite fields. Several algorithms have been proposed for this computation over the years. Until recently, the algorithm of Wiedemann [15] was the only such algorithm known to be provably efficient and reliable for computations for arbitrary fields --- particularly, over small finite fields. However, o...

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 asymptotically faster than previous known algorithms, the fastest of which required time \\Omega\\Gamma n(log q) 2 ), y or \\Omega\\Gamma n 3+2a ) in this case, which corresponds to the cost of computing x q modulo an n degree polynomial. The new algorithms factor an arbitrary polynomial in time O(n 3+a+o(1) + n 2:69+1:69a ). All measures are in fixed precision operations, that is in bit complexity. Moreover, in the special case where all the irreducible factors have the same degree, the new algorithms run in time O(n 2:69+1:69a ). In particular, one may test a polynomial for irreducibility in O(n 2:69+1:69a ) bit operations. These results generalize to the case where q = p k , where p is a small, fixed prime. 1 Introduction The expected running time of randomized algorithms...

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 domain. Zero-division is avoided by the assumption that in the domain a sum of squares of nonzero elements is always nonzero. In this paper we fully develop this method and use it to illustrate and compare a variety of means for implementing generic algorithms. Previous generic programming methods have been limited to one of compile-time, link-time, or run-time instantiation of type parameters, such as the integral domain of this algorithm, but we show how to express generic algorithms in C+ + so that all three possibilities are available using a single source code. Finally, we take advantage of the genericness to test and time the algorithm using different arithmetics, including three huge-integer arithmetic packages. 1 Introduction Given a basis B = fb1 ; : : : ; bng for R n the Gram-S...

Out of all the n x n Toeplitz matrices over a finite field of q [ elements, a fraction of exactly (1 -1 q) is non-singular.Also a fraction of exactly (1/q)(l -l/q) (1 -(q -1)/q2)'-l has generic rank O < r < n.These statements are proven with the extended Euclidean algorithm and the theory of subresultants.A matrix has generic rank r when all its leading principal minors up to dimension r are non-zero, and r is maximal.Our results have implications to the probability of success of the block Wiedemann linear system solver algorithm,which is an open question at the present time.

Article On computing greatest common divisors with polynomials given by black boxes for their evaluations Share on Authors: Angel Díaz Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile , Erich Kaltofen Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile Authors Info & Claims ISSAC '95: Proceedings of the 1995 international symposium on Symbolic and algebraic computationApril 1995 Pages 232–239https://doi.org/10.1145/220346.220375Online:01 April 1995Publication History 11citation268DownloadsMetricsTotal Citations11Total Downloads268Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields.The algorithms factor a polynomial of de reen over afinite field of constant cardi-#8,5 nality in time O(n ).Previous algorithms required time @(n2+0(1)).Thenew algorithms rely on fast matrix multiplacation techniques.More generally, to factor a polynomial of degree noverthe finite field F~with q elements, the algo-1 Sl.510gqJ ~ithmetic operations in J?9. rithms use O(n The new "baby step/giant step" techniques used in our algorithms also yield new fast practical algorithms at superquadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields. 1

This contribution to the ongoing discussion of division algorithm for residue number systems (RNS) is based on Newton iteration for computing the reciprocal. An extended RNS with twice the number of moduli provides the range required for multiplication and scaling. Separation of the algorithm description from its RNS implementation achieves a high level of modularity, and makes the complexity analysis more transparent. The number of iterations needed is logarithmic in the size of the quotient for a fixed start value. With preconditioning it becomes the logarithm of the input bit size. An implementation of the conversion to mixed radix representation is outlined in the appendix.>

Article Free Access Share on Asymptotically fast solution of Toeplitz-like singular linear systems Author: Erich Kaltofen Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile Authors Info & Claims ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computationAugust 1994 Pages 297–304https://doi.org/10.1145/190347.190431Online:01 August 1994Publication History 15citation299DownloadsMetricsTotal Citations15Total Downloads299Last 12 Months8Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Factoring high-degree polynomials by the black box Berlekamp algorithm Authors: Erich Kaltofen Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile , Austin Lobo Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile Authors Info & Claims ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computationAugust 1994 Pages 90–98https://doi.org/10.1145/190347.190371Published:01 August 1994Publication History 14citation740DownloadsMetricsTotal Citations14Total Downloads740Last 12 Months22Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

For pt.I see Proc. 3rd Ann. ACM Symp. Parallel Algms. Architecture, p. 180-91 (1991). The authors show that over any field, the solution set to a system of n linear equations in n unknowns can be computed in parallel with randomization simultaneously in poly-logarithmic time in n and with only as many processors as are utilized to multiply two n * n matrices. A time unit represents an arithmetic operation in the field. For singular systems the parallel timings are asymptotically as fast as those for non-singular systems, due to the avoidance of binary search in the matrix rank problem, except when the field has small positive characteristic; in that case, binary search is avoided at a somewhat higher processor count measure.>

Article Free Access Share on On computing determinants of matrices without divisions Author: Erich Kaltofen View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 342–349https://doi.org/10.1145/143242.143350Online:01 August 1992Publication History 29citation678DownloadsMetricsTotal Citations29Total Downloads678Last 12 Months52Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free AccessDSC: a system for distributed symbolic computation Share on Authors: A. Diaz Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile , E. Kaltofen Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile , K. Schmitz Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile , T. Valente Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New YorkView Profile Authors Info & Claims ISSAC '91: Proceedings of the 1991 international symposium on Symbolic and algebraic computationJune 1991 Pages 323–332https://doi.org/10.1145/120694.120772Online:01 June 1991Publication History 13citation168DownloadsMetricsTotal Citations13Total Downloads168Last 12 Months5Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

lems of computing the inverse, determinant, and rank of an n x 71 matrix.An individual step in our algorithms is an addition, subtraction, multiplication, division, or zero-test of elements in the field that the entries of the linear system generate.Gaussian elimination is a sequential method for all these computational problems over abstract fields, whose running time can be asymptotically related to the sequential complexity of n x n matrix multiplication (Bunch and Hopcroft 1974).We present processor efficient randomized parallel algorithms for solving non-singular systems and for inverting non-singular matrices.Csanky (1976) used Leverrier's approach to devise a parallel linear system solver, but the best processor count known for this approach exceeds by a factor of almost A the complexity of matrix multiplication (Preparata and Sarwate 1978), (Galil and Pan 1989).Leverrier's algorithm does not work for fields whose characteristic is positive and less than n, in which case the best known parallel algorithms needed by a factor of n more processors (Berkowitz 1984), (Chistov 1985).All previous parallel solutions compute the characteristic polynomial of the coefficient matrix without divisions.For this restricted algebraic model these algorithms are processor optimal, i.e., it appears not to be known how

Article Free Access Share on Effective Noether irreducibility forms and applications Author: Erich Kaltofen Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991Pages 54–63https://doi.org/10.1145/103418.103431Published:03 January 1991Publication History 2citation252DownloadsMetricsTotal Citations2Total Downloads252Last 12 Months27Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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 is studied.

We present algorithms that decompose an algebraic curve with rational coefficients in its defining bivariate equation into its irreducible real factors and its non-empty irreducible real components. We show that our algorithms are of polynomial bit complexity in the degree of the equation and the size of its coefficients. Our construction is based on computing the irreducible complex factors and then investigating high precision complex floating point coefficients of these factors and the complex norms.

Article Free Access Share on Solving systems of nonlinear polynomial equations faster Authors: J. F. Canny Univ. of California, Berkeley Univ. of California, BerkeleyView Profile , E. Kaltofen Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile , L. Yagati Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile Authors Info & Claims ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computationJuly 1989Pages 121–128https://doi.org/10.1145/74540.74556Published:17 July 1989Publication History 68citation1,515DownloadsMetricsTotal Citations68Total Downloads1,515Last 12 Months142Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

: 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 be verified in polynomial time. Atkin's method computes the order of an elliptic curve whose endomorphism ring is isomorphic to the ring of integers of a given imaginary quadratic field Q( p \\GammaD). Once an appropriate order is found, the parameters of the curve are computed as a function of a root modulo n of the Hilbert class equation for the Hilbert class field of Q( p \\GammaD). The modification we propose determines instead a root of the Watson class equation for Q( p \\GammaD) and applies a transformation to get a root of the corresponding Hilbert equation. This is a substantial improvement, in that the Watson equations have much smaller coefficients than do the Hilbert equations. 1 Introduction The Goldwasser-Kilian (1986) primality test, as modified by Atkin, allows one to efficiently ...

Algorithms are developed that adopt a novel implicit representation for multivariate polynomials and rational functions with rational coefficients, that of black boxes for their evaluation. It is shown that within this evaluation-box representation, the polynomial greatest common divisor and factorization problems as well as the problem of extracting the numerator and denominator of a rational function can be solved in random polynomial time in the usual parameters. Since the resulting evaluation programs for the goal polynomials can be converted efficiently to sparse format, solutions to sparse problems such as the sparse ration interpolation problem follow as a consequence.>

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 are given by a straight-line computation. Testing such rational numeric data for zero, for instance, is facilitated by random evaluations modulo random prime numbers. Then, auxiliary algorithms that determine the coefficients of a multivariate polynomial in a single variable are constructed. The first main result is an algorithm that produces the greatest common divisor of the input polynomials, all in straight-line representation. The second result shows how to find a straight-line program for the reduced numerator and denominator from one for the corresponding rational function. Both the algorithm for that construction and the greatest common divisor algorithm are in random polynomial time for the usual coefficient fields and output a straight-line program, which with controllably high probability correctly determines the requested answer. The running times are polynomial functions in the binary input size, the input degrees as unary numbers, and the logarithm of the inverse of the failure probability. The algorithm for straight-line programs for the numerators and denominators of rational functions implies that every degree-bounded rational function can be computed fast in parallel, that is, in polynomial size and polylogarithmic depth.

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)$ processors, where $M(n)$ is the number of processors required for multiplying $n \times n$ matrices over the semi-ring R in $O(\log n)$ time.

We discuss the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations. Our system is capable of performing rational arithmetic on, evaluating, differentiating, taking greatest common divisors of, and factoring polynomials in straight-line format. The straight-line results can also be converted to standard, sparse format. We show by example that our system can handle problems for which conventional methods lead to excessive intermediate expression swell.

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 shows how to compute a higher order partial derivative in a single variable. The other two theorems impose the degree of the output polynomial as a parameter of the length of the output program. First it is shown that if a straight-line program computes an arbitrary power of a multivariate polynomial, that polynomial also admits a polynomial bounded straight-line computation. Second, any factor of a multivariate polynomial given by a division-free straight-line program with relatively prime co-factor also admits a straight-line computation of length polynomial in the input length and the degree of the factor. This result is based on a new Hensel lifting process, one where only one factor image is lifted back to the original factor. As an application we get that the greatest common divisor of polynomials given by a division-free straight-line program has polynomial straight-line complexity in terms of the input length and its own degree.

Valiant [24] introduced the notion of a family of p-computable polynomials as those multivariate polynomials of polynomially-bounded degree and straight-line computation length. He raised the question of whether p-computable families would be closed under natural mathematical operations and showed that this is true for taking repeated partial derivatives inasingle variable,

We develop an algorithm for the factorization of a multivariate polynomial represented by a straight-line program into its irreducible factors represented as sparse polynomials. Our algorithm is in random polynomial-time for the usual coefficient fields and outputs with controllably high probability the correct factorization. It only requires an a priori bound for the total degree of the input and over rational numbers a bound on the size of the polynomial coefficients.

We develop algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation. Our algorithms are in random polynomial-time for the usual coefficient fields and output with controllably high probability the correct result which for the GCD problem is a straight-line program determining the GCD of the inputs and for the conversion algorithm is the sparse representation of the input. The algorithms only require an a priori bound for the total degrees of the inputs. Over rational numbers the conversion algorithm also needs a bound on the size of the polynomial coefficients. As specializations we get, e.g., random polynomial-time algorithms for computing the sparse GCD of polynomial determinants or for computing the sparse solution of a linear system whose coefficients are given by formulas.

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 polynomial-time in the total degree of f and the coefficient lengths of f to factoring a univariate integral polynomial. Together with A. Lenstra’s,.H. Lenstra’s and L. Lovász’ polynomial-time factorization algorithm for univariate integral polynomials [Math. Ann., 261 (1982), pp. 515–534] this algorithm implies the following theorem. Factoring an integral polynomial with a fixed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree and the size of its coefficients. Our algorithm can be generalized to factoring multivariate polynomials with coefficients in algebraic number fields and finite fields in polynomial-time. We also present a different algorithm, based on an effective version of a Hilbert Irreducibility Theorem, which polynomial-time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polynomials for irreduciblity.

A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. This class contains as subclasses the Swinnerton-Dyer polynomials discussed by Berlekamp and a subset of the cyclotomic polynomials. Aside from shedding light on the complexity of polynomial factorization this class is also useful in testing implementations of the Berlekamp–Hensel and related algorithms.

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 lengths to factoring a univariate integer polynomial. Together with A. Lenstra's, H. Lenstra's and L. Lovasz' polynomial-time factorization algorithm for univariate integer polynomials and the author's multivariate to bivariate reduction the new algorithm implies the following theorem. Factoring a polynomial with a fixed number of variables into irreducibles, except for the constant factors, can be accomplished in time polynomial in the total degree and the size of its coefficients. The new algorithm can be generalized to reducing multivariate factorization directly to univariate factorization and to factoring multivariate polynomials with coefficients in algebraic number fields and finite fields in polynomial time.

Given an arbitrary but fixed integer r ≥ 3. We show that testing r-variate polynomials with integer coefficients for irreducibility is m-reducible in polynomial time of the total degree and the largest coefficient length to testing bivariate polynomials for irreducibility. Factoring r-variate polynomials into irreducibles is polynomial time Turing-reducible to completely factoring bivariate polynomials.