@article{kaltofen_2022, title={Sparse Polynomial Hermite Interpolation}, DOI={10.1145/3476446.3535501}, abstractNote={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.}, journal={PROCEEDINGS OF THE 2022 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2022}, author={Kaltofen, Erich L.}, year={2022}, pages={469–478} }
@article{kaltofen_2022, title={The GKR Protocol Revisited: Nearly Optimal Prover-Complexity For Polynomial-Time Wiring Algorithms and For Primality Testing in n(1/2+o(1)) Rounds}, DOI={10.1145/3476446.3536183}, abstractNote={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. The verifier time-complexity of GKR grows linearly in the depth of the circuit. For deep circuits such as the Miller-Rabin integer primality test of an n-bit integer, the large number of rounds may interfere with soundness guarantees after the application of the Fiat-Shamir heuristic. We re-arrange the circuit evaluation problem by the baby-steps/giant-steps method to achieve a depth of n1/2+o(1), at prover cost n2+o(1) bit complexity and communication and verifier cost n3/2+o(1).}, journal={PROCEEDINGS OF THE 2022 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2022}, author={Kaltofen, Erich L.}, year={2022}, pages={177–186} }
@article{kaltofen_2021, title={Foreword}, volume={105}, ISSN={["1095-855X"]}, DOI={10.1016/j.jsc.2020.04.006}, abstractNote={We consider the problem of computing the nearest matrix polynomial with a non-trivial Smith Normal Form. We show that computing the Smith form of a matrix polynomial is amenable to numeric computation as an optimization problem. Furthermore, we describe an effective optimization technique to find a nearby matrix polynomial with a non-trivial Smith form. The results are then generalized to include the computation of a matrix polynomial having a maximum specified number of ones in the Smith Form (i.e., with a maximum specified McCoy rank).We discuss the geometry and existence of solutions and how our results can be used for an error analysis. We develop an optimization-based approach and demonstrate an iterative numerical method for computing a nearby matrix polynomial with the desired spectral properties. We also describe an implementation of our algorithms and demonstrate the robustness with examples in Maple.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, Erich L.}, year={2021}, pages={1–3} }
@article{imamoglu_kaltofen_2021, title={On computing the degree of a Chebyshev Polynomial from its value}, volume={104}, ISSN={["1095-855X"]}, DOI={10.1016/j.jsc.2020.04.011}, abstractNote={Algorithms for interpolating a polynomial f from its evaluation points whose running time depends on the sparsity t of the polynomial when it is represented as a linear combination of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients are given by Lakshman and Saunders (1995), Kaltofen and Lee (2003) and Arnold and Kaltofen (2015). The term degrees are computed from values of Chebyshev Polynomials of those degrees. We give an algorithm that computes those degrees in the manner of the Pohlig and Hellman algorithm (1978) for computing discrete logarithms modulo a prime number p when the factorization of p−1 (or p+1) has small prime factors, that is, when p−1 (or p+1) is smooth. Our algorithm can determine the Chebyshev degrees modulo such primes in bit complexity log(p)O(1) times the squareroot of the largest prime factor of p−1 (or p+1).}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Imamoglu, Erdal and Kaltofen, Erich L.}, year={2021}, pages={159–167} }
@article{kaltofen_yang_2021, title={Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding}, volume={67}, ISSN={["1557-9654"]}, DOI={10.1109/TIT.2020.3027036}, abstractNote={We present sparse interpolation algorithms for recovering a polynomial with $\le B$ terms from $N$ evaluations at distinct values for the variable when $\le E$ of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars $ \mathsf {K}$ and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of $ \mathsf {K}$ is $\ne 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 = \lfloor \frac {4}{3} E + 2 \rfloor 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 = \lfloor \frac {3}{2} E + 2 \rfloor 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 \lfloor \frac {E}{13} + 1 \rfloor $ for $B = 3$ and $E \ge 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.}, number={1}, journal={IEEE TRANSACTIONS ON INFORMATION THEORY}, author={Kaltofen, Erich L. and Yang, Zhi-Hong}, year={2021}, month={Jan}, pages={232–243} }
@article{imamoglu_kaltofen_2020, title={A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis}, volume={54}, ISSN={["1932-2240"]}, DOI={10.1145/3465002.3465003}, abstractNote={The sparsity t≪ deg(f) with respect to the basis Pn has been exploited—since [9] —in interpolation algorithms that reconstruct the degree/coefficient expansion (δj, cj)1≤j≤t from values ai = f(γi) at the arguments x ← γi ∈ K. Current algorithms for standard and Chebyshev bases use i = 1, . . . , N = t + B values when an upper bound B ≥ t is provided on input. The sparsity t can also be computed “on-the-fly” from N = 2t+ 1 values by a randomized algorithm which fails with probability O(ǫ deg(f)), where ǫ≪ 1 can be chosen on input. See [3] for a list of references. This note considers Dickson Polynomials for the basis in which a sparse representation is sought. Wang and Yucas [10, Remark 2.5] define the n-th degree Dickson Polynomials Dn,k(x, a) ∈ K[x] of the (k + 1)’st kind for a parameter a ∈ K, a 6= 0, and k ∈ Z≥0, k 6= 2 recursively as as follows:}, number={4}, journal={ACM COMMUNICATIONS IN COMPUTER ALGEBRA}, author={Imamoglu, Erdal and Kaltofen, Erich L.}, year={2020}, month={Dec}, pages={125–128} }
@article{giesbrecht_haraldson_kaltofen_2019, title={Computing Approximate Greatest Common Right Divisors of Differential Polynomials}, ISSN={1615-3375 1615-3383}, url={http://dx.doi.org/10.1007/s10208-019-09422-2}, DOI={10.1007/s10208-019-09422-2}, abstractNote={Differential (Ore) type polynomials with “approximate” polynomial coefficients are introduced. These provide an effective notion of approximate differential operators, with a strong algebraic structure. We introduce the approximate greatest common right divisor problem (GCRD) of differential polynomials, as a non-commutative generalization of the well-studied approximate GCD problem. Given two differential polynomials, we present an algorithm to find nearby differential polynomials with a non-trivial GCRD, where nearby is defined with respect to a suitable coefficient norm. Intuitively, given two linear differential polynomials as input, the (approximate) GCRD problem corresponds to finding the (approximate) differential polynomial whose solution space is the intersection of the solution spaces of the two inputs. The approximate GCRD problem is proven to be locally well posed. A method based on the singular value decomposition of a differential Sylvester matrix is developed to produce an initial approximation of the GCRD. With a sufficiently good initial approximation, Newton iteration is shown to converge quadratically to an optimal solution. Finally, sufficient conditions for existence of a solution to the global problem are presented along with examples demonstrating that no solution exists when these conditions are not satisfied.}, journal={Foundations of Computational Mathematics}, publisher={Springer Science and Business Media LLC}, author={Giesbrecht, Mark and Haraldson, Joseph and Kaltofen, Erich}, year={2019}, month={Jun} }
@article{dumas_kaltofen_lucas_pernet_2019, title={Elimination-based certificates for triangular equivalence and rank profiles}, volume={98}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2019.07.013}, abstractNote={In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable somebody to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead. We first provide quadratic time and space non-interactive certificates saving the logarithmic factors of previously known ones. Then we propose interactive certificates for the same problems whose Monte Carlo verification complexity requires a small constant number of matrix-vector multiplications, a linear space, and a linear number of extra field operations, with a linear number of interactions. As an application we also give an interactive protocol, certifying the determinant or the signature of dense matrices, faster for the Prover than the best previously known one. Finally we give linear space and constant round certificates for the row or column rank profiles.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Dumas, Jean-Guillaume and Kaltofen, Erich and Lucas, David and Pernet, Clement}, year={2019}, pages={246–269} }
@article{imamoglu_kaltofen_yang_2018, title={Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases}, DOI={10.1145/3208976.3208999}, abstractNote={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.}, journal={ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION}, author={Imamoglu, Erdal and Kaltofen, Erich L. and Yang, Zhengfeng}, year={2018}, pages={223–230} }
@inproceedings{kaltofen_pernet_storjohann_waddell_2017, title={Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction}, ISBN={9781450350648}, url={http://dx.doi.org/10.1145/3087604.3087645}, DOI={10.1145/3087604.3087645}, abstractNote={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. Incorporating our two counts we develop a combined early termination algorithm. We then specialize the algorithm in [Boyer and Kaltofen, Proc. SNC 2014] for parametric linear system solving to the recovery of a vector of rational functions, 1/g(u) f(u), from its evaluations. Thus, if the rational function vector is the solution to a full rank linear system our early termination strategy applies and we may recover it from fewer evaluations than generalized Welch/Berlekamp decoding. If we allow evaluations at poles (roots of g) there are examples where the Cabay count is not sufficient to recover the rational function vector from just its evaluations. This problem is solved if in addition to indicating that an evaluation point is a pole, the black box gives information about the numerators of the solution at the evaluation point.}, booktitle={Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '17}, publisher={ACM Press}, author={Kaltofen, Erich L. and Pernet, Clément and Storjohann, Arne and Waddell, Cleveland}, year={2017} }
@inproceedings{dumas_kaltofen_villard_zhi_2017, title={Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits}, ISBN={9781450350648}, url={http://dx.doi.org/10.1145/3087604.3087640}, DOI={10.1145/3087604.3087640}, abstractNote={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).}, booktitle={Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '17}, publisher={ACM Press}, author={Dumas, Jean-Guillaume and Kaltofen, Erich L. and Villard, Gilles and Zhi, Lihong}, year={2017} }
@article{dumas_kaltofen_thome_villard_2016, title={Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix}, DOI={10.1145/2930889.2930908}, abstractNote={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.}, journal={PROCEEDINGS OF THE 2016 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC 2016)}, author={Dumas, Jean -Guillaume and Kaltofen, Erich and Thome, Emmanuel and Villard, Gilles}, year={2016}, pages={199–206} }
@inproceedings{hao_kaltofen_zhi_2016, title={Numerical Sparsity Determination and Early Termination}, ISBN={9781450343800}, url={http://dx.doi.org/10.1145/2930889.2930924}, DOI={10.1145/2930889.2930924}, abstractNote={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. Our algorithm still has to make a guess, the number ζ of oversamples, and we show by example that if ζ is guessed too small, premature termination can occur, but our criterion is numerically more accurate than that by Kaltofen, Lee and Yang (Proc. SNC 2011, ACM [12]), but not as efficiently computable. For heuristic justification one has available the multivariate early termination theorem by Kaltofen and Lee (JSC vol. 36(3--4) 2003 [11]) for exact arithmetic, and the numeric Schwartz-Zippel Lemma by Kaltofen, Yang and Zhi (Proc. SNC 2007, ACM [13]). A main contribution here is a modified proof of the Theorem by Kaltofen and Lee that permits starting the sequence at the point (1,...,1), for scalar fields of characteristic ≠ 2 (in characteristic 2 counter-examples are given).}, booktitle={Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '16}, publisher={ACM Press}, author={Hao, Zhiwei and Kaltofen, Erich L. and Zhi, Lihong}, year={2016} }
@article{kaltofen_yang_2016, title={Sparse multivariate function recovery with a small number of evaluations}, volume={75}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2015.11.015}, abstractNote={In Kaltofen and Yang (2014) we give an algorithm based algebraic error-correcting decoding for multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (“outliers”). Our 2014 algorithm can interpolate a sparse multivariate rational function from evaluations where the error rate 1/q is quite high, say q=5. For the algorithm with exact arithmetic and exact values at non-erroneous points, one avoids quadratic oversampling by using random evaluation points. Here we give the full probabilistic analysis for this fact, thus providing the missing proof to Theorem 2.1 in Section 2 of our ISSAC 2014 paper. Our argumentation already applies to our original 2007 sparse rational function interpolation algorithm (Kaltofen et al., 2007), where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T+O(1) evaluations rather than O(T2) (cf. Candès and Tao sparse sensing), the latter of which we have proved in 2007. Here we prove that T+O(1) evaluations at random points indeed suffice.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, Erich L. and Yang, Zhengfeng}, year={2016}, pages={209–218} }
@inproceedings{arnold_kaltofen_2015, title={Error-Correcting Sparse Interpolation in the Chebyshev Basis}, ISBN={9781450334358}, url={http://dx.doi.org/10.1145/2755996.2756652}, DOI={10.1145/2755996.2756652}, abstractNote={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.}, booktitle={Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '15}, publisher={ACM Press}, author={Arnold, Andrew and Kaltofen, Erich L.}, year={2015} }
@book{dumas_kaltofen_pernet_2015, place={New York, NY}, title={PASCO '15 Proceedings of the 2015 International Workshop on Parallel Symbolic Computation}, publisher={Association for Computing Machinery}, year={2015} }
@inproceedings{kaltofen_2014, title={Cleaning-up data for sparse model synthesis}, ISBN={9781450329637}, url={http://dx.doi.org/10.1145/2631948.2631949}, DOI={10.1145/2631948.2631949}, abstractNote={The discipline of symbolic computation contributes to mathematical model synthesis in several ways. One is the pioneering creation of interpolation algorithms that can account for sparsity in the resulting multi-dimensional models, for example, by Zippel [12], Ben-Or and Tiwari [1], and in their recent numerical counterparts by Giesbrecht-Labahn-Lee [5] and Kaltofen-Yang-Zhi [9].}, booktitle={Proceedings of the 2014 Symposium on Symbolic-Numeric Computation - SNC '14}, publisher={ACM Press}, author={Kaltofen, Erich L.}, year={2014} }
@inproceedings{dumas_kaltofen_2014, title={Essentially optimal interactive certificates in linear algebra}, ISBN={9781450325011}, url={http://dx.doi.org/10.1145/2608628.2608644}, DOI={10.1145/2608628.2608644}, abstractNote={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 give algorithms that compute essentially optimal certificates for the positive semidefiniteness, Frobenius form, characteristic and minimal polynomial of an n × n dense integer matrix A. Our certificates can be verified in Monte-Carlo bit complexity (n2 log ||A||)1+o(1), where log ||A|| is the bit size of the integer entries, solving an open problem in [Kaltofen, Nehring, Saunders, Proc. ISSAC 2011] subject to computational hardness assumptions.
Second, we give algorithms that compute certificates for the rank of sparse or structured n × n matrices over an abstract field, whose Monte Carlo verification complexity is 2 matrix-times-vector products + n1+o(1) arithmetic operations in the field. For example, if the n × n input matrix is sparse with n1+o(1) non-zero entries, our rank certificate can be verified in n1+o(1) field operations. This extends also to integer matrices with only an extra log ||A||1+o(1) factor.
All our certificates are based on interactive verification protocols with the interaction removed by a Fiat-Shamir identification heuristic. The validity of our verification procedure is subject to standard computational hardness assumptions from cryptography.}, booktitle={Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14}, publisher={ACM Press}, author={Dumas, Jean-Guillaume and Kaltofen, Erich}, year={2014} }
@inproceedings{boyer_kaltofen_2014, title={Numerical linear system solving with parametric entries by error correction}, ISBN={9781450329637}, url={http://dx.doi.org/10.1145/2631948.2631956}, DOI={10.1145/2631948.2631956}, abstractNote={We consider the problem of solving a full rank consistent linear system A(u)x = b(u) where the m x n matrix A and the m-dimensional vector b has entries that are polynomials in u over a field. We give an algorithm that computes the unique solution x = f(u)/g(u), which is a vector of rational functions, by evaluating the parameter u at distinct points. Those points ξλ where the matrix A evaluates to a matrix A(ξλ), with entries over the scalar field, of lower rank, or in the numeric setting to an ill-conditioned matrix, are not identified but accounted for by error-correcting code techniques. We also correct true errors where the evaluation at some u = ξλ results in an erroneous, possibly full rank consistent and well-conditioned scalar linear system. Our algorithm generalizes Welch/Berlekamp decoding of Reed/Solomon error correcting codes and their numeric floating point counterparts.
We have implemented our algorithms with floating point arithmetic. For the determination of the exact numerator and denominator degrees and number of errors we use singular values based numeric rank computations. The arising linear systems for the error-corrected parametric solution are demonstrated to be well-conditioned even when the input scalars have noise. In several initial experiments we have shown that our approach is numerically stable even for larger systems m = n = 100, provided the degrees in the solution are small (≤ 2). For smaller systems m = n = 10 with higher degrees (≤ 20) the algorithm works similarly to rational function recovery. Our implementation can correct 13 true errors in both settings.}, booktitle={Proceedings of the 2014 Symposium on Symbolic-Numeric Computation - SNC '14}, publisher={ACM Press}, author={Boyer, Brice and Kaltofen, Erich L.}, year={2014} }
@inbook{boyer_comer_kaltofen_2014, title={Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations}, ISBN={9783662437988 9783662437995}, url={http://dx.doi.org/10.1007/978-3-662-43799-5_16}, DOI={10.1007/978-3-662-43799-5_16}, booktitle={Computer Mathematics}, publisher={Springer Berlin Heidelberg}, author={Boyer, Brice and Comer, Matthew T. and Kaltofen, Erich L.}, year={2014}, pages={183–197} }
@inproceedings{kaltofen_yang_2014, title={Sparse multivariate function recovery with a high error rate in the evaluations}, ISBN={9781450325011}, url={http://dx.doi.org/10.1145/2608628.2608637}, DOI={10.1145/2608628.2608637}, abstractNote={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).
For the algorithm with exact arithmetic and exact values at non-erroneous points, we provide a proof that for random evaluations one can avoid quadratic oversampling. Our argument already applies to our original 2007 sparse rational function interpolation algorithm [Kaltofen, Yang and Zhi, Proc. SNC 2007], where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T +O(1) evaluations rather than the proven O(T2) (cf. Candès and Tao sparse sensing). Here we finally can give the probabilistic analysis for this fact.}, booktitle={Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14}, publisher={ACM Press}, author={Kaltofen, Erich L. and Yang, Zhengfeng}, year={2014} }
@inproceedings{kaltofen_pernet_2014, title={Sparse polynomial interpolation codes and their decoding beyond half the minimum distance}, ISBN={9781450325011}, url={http://dx.doi.org/10.1145/2608628.2608660}, DOI={10.1145/2608628.2608660}, abstractNote={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.
Our new polynomial-time list decoding algorithm uses sub-sequences of the received evaluations indexed by an arithmetic progression, allowing the decoding for a larger radius, that is, more errors in the evaluations while returning a list of candidate sparse polynomials. We quantify this improvement for all typically small values of number of terms and number of errors, and provide a worst case asymptotic analysis of this improvement. For instance, for sparsity T = 5 with ≤ 10 errors we can list decode in polynomial-time from 74 values of the polynomial with unknown terms, whereas our earlier algorithm required 2T(E + 1) = 110 evaluations.
We then propose two variations of these codes in characteristic zero, where appropriate choices of values for the variable yield a much larger minimal distance: the code-word length minus twice the sparsity.}, booktitle={Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14}, publisher={ACM Press}, author={Kaltofen, Erich L. and Pernet, Clément}, year={2014} }
@inbook{kaltofen_2014, title={Symbolic Computation and Complexity Theory Transcript of My Talk}, ISBN={9783662437988 9783662437995}, url={http://dx.doi.org/10.1007/978-3-662-43799-5_1}, DOI={10.1007/978-3-662-43799-5_1}, booktitle={Computer Mathematics}, publisher={Springer Berlin Heidelberg}, author={Kaltofen, Erich L.}, year={2014}, pages={3–7} }
@article{kaltofen_yuhasz_2013, title={A fraction free Matrix Berlekamp/Massey algorithm}, volume={439}, ISSN={["1873-1856"]}, DOI={10.1016/j.laa.2013.06.016}, abstractNote={We describe a fraction free version of the Matrix Berlekamp/Massey algorithm. The algorithm computes a minimal matrix generator of linearly generated square matrix sequences in an integral domain. The algorithm performs all operations in the integral domain, so all divisions performed are exact. For scalar sequences, the matrix algorithm specializes to a different algorithm than the algorithm currently in the literature. This new scalar algorithm has smaller intermediate values than the known fraction free Berlekamp/Massey algorithm.}, number={9}, journal={LINEAR ALGEBRA AND ITS APPLICATIONS}, author={Kaltofen, Erich and Yuhasz, George}, year={2013}, month={Nov}, pages={2515–2526} }
@inbook{kaltofen_lecerf_2013, place={Boca Raton, Florida}, title={Factorization of multivariate polynomials}, booktitle={Handbook of Finite Fields}, publisher={CRC Press, Taylor & Francis Group}, author={Kaltofen, Erich and Lecerf, Grégoire}, editor={Mullen, Gary L. and Panario, DanielEditors}, year={2013}, pages={382–392} }
@article{kaltofen_yuhasz_2013, title={On the Matrix Berlekamp-Massey Algorithm}, volume={9}, ISSN={["1549-6333"]}, DOI={10.1145/2500122}, abstractNote={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.}, number={4}, journal={ACM TRANSACTIONS ON ALGORITHMS}, author={Kaltofen, Erich and Yuhasz, George}, year={2013}, month={Sep} }
@inproceedings{kaltofen_yang_2013, title={Sparse multivariate function recovery from values with noise and outlier errors}, ISBN={9781450320597}, url={http://dx.doi.org/10.1145/2465506.2465524}, DOI={10.1145/2465506.2465524}, abstractNote={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.}, booktitle={Proceedings of the 38th international symposium on International symposium on symbolic and algebraic computation - ISSAC '13}, publisher={ACM Press}, author={Kaltofen, Erich L. and Yang, Zhengfeng}, year={2013} }
@inproceedings{guo_kaltofen_zhi_2012, title={Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions}, ISBN={9781450312691}, url={http://dx.doi.org/10.1145/2442829.2442859}, DOI={10.1145/2442829.2442859}, abstractNote={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.
The literature has many famous examples of impossibility of SOS representability including Motzkin's, Robinson's, Choi's and Lam's polynomials, and Reznick's lower degree bounds on uniform denominators, e.g., powers of the sum-of-squares of each variable. Our work on exact certificates for positive semidefiniteness allows for non-uniform denominators, which can have lower degree and are often easier to convert to exact identities. Here we demonstrate our algorithm by computing certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively. We can also certify impossibility of base polynomials in the denominator of restricted term structure, for instance as in Landau's reduction by one less variable.}, booktitle={Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation - ISSAC '12}, publisher={ACM Press}, author={Guo, Feng and Kaltofen, Erich L. and Zhi, Lihong}, year={2012} }
@article{kaltofen_li_yang_zhi_2012, title={Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients}, volume={47}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/j.jsc.2011.08.002}, DOI={10.1016/j.jsc.2011.08.002}, abstractNote={We present a hybrid symbolic-numeric algorithm for certifying a polynomial or rational function with rational coefficients to be non-negative for all real values of the variables by computing a representation for it as a fraction of two polynomial sum-of-squares (SOS) with rational coefficients. Our new approach turns the earlier methods by Peyrl and Parrilo at SNC’07 and ours at ISSAC’08 both based on polynomial SOS, which do not always exist, into a universal algorithm for all inputs via Artin’s theorem. Furthermore, we scrutinize the all-important process of converting the numerical SOS numerators and denominators produced by block semidefinite programming into an exact rational identity. We improve on our own Newton iteration-based high precision refinement algorithm by compressing the initial Gram matrices and by deploying rational vector recovery aside from orthogonal projection. We successfully demonstrate our algorithm on (1) various exceptional SOS problems with necessary polynomial denominators from the literature and on (2) very large (thousands of variables) SOS lower bound certificates for Rump’s model problem (up to n=18, factor degree=17).}, number={1}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Kaltofen, Erich L. and Li, Bin and Yang, Zhengfeng and Zhi, Lihong}, year={2012}, month={Jan}, pages={1–15} }
@article{comer_kaltofen_2012, title={On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field}, volume={47}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2011.09.008}, abstractNote={We derive an explicit count for the number of singular n×n Hankel (Toeplitz) matrices whose entries range over a finite field with q elements by observing the execution of the Berlekamp/Massey algorithm on its elements. Our method yields explicit counts also when some entries above or on the anti-diagonal (diagonal) are fixed. For example, the number of singular n×n Toeplitz matrices with 0’s on the diagonal is q2n−3+qn−1−qn−2. We also derive the count for all n×n Hankel matrices of rank r with generic rank profile, i.e., whose first r leading principal submatrices are non-singular and the rest are singular, namely qr(q−1)r in the case rt-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 also investigate the problem of recovering the minimal linear generator from a sequence of field elements that are linearly generated, but where again e ≤ E elements are erroneous. We show that there exist sequences of < 2t(2e + 1) elements, such that two distinct generators of length t satisfy the linear recurrence up to e faults, at least if the field has characteristic ≠ 2. Uniqueness can be proven (for any field characteristic) for length ≥ 2t(2e + 1) of the sequence with e errors. Finally, we present the Majority Rule Berlekamp/Massey algorithm, which can recover the unique minimal linear generator of degree t when given bounds T ≥ t and E ≥ e and the initial sequence segment of 2T(2E + 1) elements. Our algorithm also corrects the sequence segment. The Majority Rule algorithm yields a unique sparse interpolant for the first problem.
The algorithms are applied to sparse interpolation algorithms with numeric noise, into which we now can bring outlier errors in the values.}, booktitle={Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation - ISSAC '12}, publisher={ACM Press}, author={Comer, Matthew T. and Kaltofen, Erich L. and Pernet, Clément}, year={2012} }
@article{johnson_kaltofen_park_2012, title={Special Issue on Symbolic and Algebraic Computation Foundations, Algorithmics and Applications: ISSAC 2009}, volume={47}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2011.12.006}, number={7}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Johnson, Jeremy R. and Kaltofen, Erich and Park, Hyungju}, year={2012}, month={Jul}, pages={751–751} }
@inproceedings{kaltofen_lee_yang_2011, title={Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation}, ISBN={9781450305150}, url={http://dx.doi.org/10.1145/2331684.2331704}, DOI={10.1145/2331684.2331704}, abstractNote={We investigate our early termination criterion for sparse polynomial interpolation when substantial noise is present in the values of the polynomial. Our criterion in the exact case uses Monte Carlo randomization which introduces a second source of error. We harness the Gohberg-Semencul formula for the inverse of a Hankel matrix to compute estimates for the structured condition numbers of all arising Hankel matrices in quadratic arithmetic time overall, and explain how false ill-conditionedness can arise from our randomizations. Finally, we demonstrate by experiments that our condition number estimates lead to a viable termination criterion for polynomials with about 20 non-zero terms and of degree about 100, even in the presence of noise of relative magnitude 10-5.}, booktitle={Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation - SNC '11}, publisher={ACM Press}, author={Kaltofen, Erich L. and Lee, Wen-shin and Yang, Zhengfeng}, year={2011} }
@inproceedings{kaltofen_nehring_saunders_2011, title={Quadratic-time certificates in linear algebra}, ISBN={9781450306751}, url={http://dx.doi.org/10.1145/1993886.1993915}, DOI={10.1145/1993886.1993915}, abstractNote={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.
In addition, we give certificates of the same space and randomized validation time complexity for the Frobenius form, which includes the characteristic and minimal polynomial. For determinant and rank we have certificates of essentially-quadratic binary space and time complexity via Storjohann's algorithms.}, booktitle={Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11}, publisher={ACM Press}, author={Kaltofen, Erich L. and Nehring, Michael and Saunders, B. David}, year={2011} }
@inproceedings{kaltofen_nehring_2011, title={Supersparse black box rational function interpolation}, ISBN={9781450306751}, url={http://dx.doi.org/10.1145/1993886.1993916}, DOI={10.1145/1993886.1993916}, abstractNote={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.
The algorithm, as presented, is conjectured to be polylogarithmic in the degree, but exponential in the number of terms. Therefore, it is very effective for rational functions with a small number of non-zero terms, such as the ratio of binomials, but it quickly becomes ineffective for a high number of terms.
The algorithm is oblivious to whether the numerator and denominator have a common factor. The algorithm will recover the sparse form of the rational function, rather than the reduced form, which could be dense. We have experimentally tested the algorithm in the case of under 10 terms in numerator and denominator combined and observed its conjectured high efficiency.}, booktitle={Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11}, publisher={ACM Press}, author={Kaltofen, Erich L. and Nehring, Michael}, year={2011} }
@misc{grenet_kaltofen_koiran_portier_2011, title={Symmetric determinantal representation of formulas and weakly skew circuits}, ISBN={9780821852286 9780821882351}, ISSN={1098-3627 0271-4132}, url={http://dx.doi.org/10.1090/conm/556/11008}, DOI={10.1090/conm/556/11008}, journal={Randomization, Relaxation, and Complexity in Polynomial Equation Solving}, publisher={American Mathematical Society}, author={Grenet, Bruno and Kaltofen, Erich and Koiran, Pascal and Portier, Natacha}, year={2011}, pages={61–96} }
@inproceedings{grenet_kaltofen_koiran_portier_2011, place={Germany}, title={Symmetric determinantal representation of weakly skew circuits}, booktitle={Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, author={Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha}, editor={Dürr, Christoph and Schwentick, ThomasEditors}, year={2011}, pages={543–554} }
@inbook{kaltofen_2011, title={The “Seven Dwarfs” of Symbolic Computation}, ISBN={9783709107935 9783709107942}, ISSN={0943-853X}, url={http://dx.doi.org/10.1007/978-3-7091-0794-2_5}, DOI={10.1007/978-3-7091-0794-2_5}, abstractNote={We present the Seven Dwarfs of Symbolic Computation, which are sequential and parallel algorithmic methods that today carry a great majority of all exact and hybrid symbolic compute cycles. We will elaborate on each dwarf and compare with Colella’s seven and the Berkeley team’s thirteen dwarfs of scientific computing.}, booktitle={Texts & Monographs in Symbolic Computation}, publisher={Springer Vienna}, author={Kaltofen, Erich L.}, year={2011}, month={Oct}, pages={95–104} }
@inproceedings{hutton_kaltofen_zhi_2010, title={Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method}, ISBN={9781450301503}, url={http://dx.doi.org/10.1145/1837934.1837979}, DOI={10.1145/1837934.1837979}, abstractNote={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. The radius of positive (or negative) semidefiniteness is the distance to the nearest polynomial with a real root, which has been thoroughly studied before. We solve this problem by parameterized Lagrangian multipliers and Karush-Kuhn-Tucker conditions. Our algorithms can compute the radius for several simultaneous inequalities including possibly additional linear coefficient constraints. Our distance measure is the weighted Euclidean coefficient norm, but we also discuss several formulas for the weighted infinity and 1-norms. The computation of the nearest polynomial with a real root can be interpreted as a dual of Seidenberg's method that decides if a real hypersurface contains a real point. Sums-of-squares rational lower bound certificates for the radius of semidefiniteness provide a new approach to solving Seidenberg's problem, especially when the coefficients are numeric. They also offer a surprising alternative sum-of-squares proof for those polynomials that themselves cannot be represented by a polynomial sum-of-squares but that have a positive distance to the nearest indefinite polynomial.}, booktitle={Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation - ISSAC '10}, publisher={ACM Press}, author={Hutton, Sharon and Kaltofen, Erich L. and Zhi, Lihong}, year={2010} }
@article{kaltofen_lavin_2010, title={Efficiently Certifying Non-Integer Powers}, volume={19}, ISSN={["1420-8954"]}, DOI={10.1007/s00037-010-0297-x}, number={3}, journal={COMPUTATIONAL COMPLEXITY}, author={Kaltofen, Erich and Lavin, Mark}, year={2010}, month={Sep}, pages={355–366} }
@inproceedings{kaltofen_2010, title={Fifteen years after DSC and WLSS2 what parallel computations I do today}, ISBN={9781450300674}, url={http://dx.doi.org/10.1145/1837210.1837213}, DOI={10.1145/1837210.1837213}, abstractNote={A second wave of parallel and distributed computing research is rolling in. Today's multicore/multiprocessor computers facilitate everyone's parallel execution. In the mid 1990s, manufactures of expensive main-frame parallel computers faltered and computer science focused on the Internet and the computing grid. After a ten year hiatus, the Parallel Symbolic Computation Conference (PASCO) is awakening with new vigor. I shall look back on the highlights of my own research on theoretical and practical aspects of parallel and distributed symbolic computation, and forward to what is to come by example of several current projects. An important technique in symbolic computation is the evaluation/interpolation paradigm, and multivariate sparse polynomial parallel interpolation constitutes a keystone operation, for which we present a new algorithm. Several embarrassingly parallel searches for special polynomials and exact sum-of-squares certificates have exposed issues in even today's multiprocessor architectures. Solutions are in both software and hardware. Finally, we propose the paradigm of interactive symbolic supercomputing, a symbolic computation environment analog of the STAR-P Matlab platform.}, booktitle={Proceedings of the 4th International Workshop on Parallel and Symbolic Computation - PASCO '10}, publisher={ACM Press}, author={Kaltofen, Erich L.}, year={2010} }
@book{kaltofen_2010, title={The Role of Symbolic, Numeric and Algebraic Computation in Cyber-Enabled Discovery and Innovation (CDI)}, journal={Future Directions of Symbolic Computation Research And Their Applications to the Domain Sciences}, institution={University of Rhode Island}, author={Kaltofen, Erich L.}, year={2010} }
@inproceedings{kaltofen_yang_zhi_2009, title={A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions}, ISBN={9781605586649}, url={http://dx.doi.org/10.1145/1577190.1577204}, DOI={10.1145/1577190.1577204}, abstractNote={For a proof of the monotone column permanent (MCP)conjecture for dimension 4 it is sufficient to show that 4 polynomials, which come from the permanents of real matrices, are nonnegative for all real values of the variables, where the degrees and the number of the variables of these polynomials are all 8. Here we apply a hybrid symbolic-numerical algorithm for certifying that these polynomials can be written as an exact fraction of two polynomial sums-of-squares (SOS) with rational coefficients.}, booktitle={Proceedings of the 2009 conference on Symbolic numeric computation - SNC '09}, publisher={ACM Press}, author={Kaltofen, Erich and Yang, Zhengfeng and Zhi, Lihong}, year={2009} }
@article{kaltofen_may_yang_zhi_2008, title={Approximate factorization of multivariate polynomials using singular value decomposition}, volume={43}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2007.11.005}, abstractNote={We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10−3).}, number={5}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, Erich and May, John P. and Yang, Zhengfeng and Zhi, Lihong}, year={2008}, month={May}, pages={359–376} }
@inproceedings{kaltofen_li_yang_zhi_2008, title={Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars}, ISBN={9781595939043}, url={http://dx.doi.org/10.1145/1390768.1390792}, DOI={10.1145/1390768.1390792}, abstractNote={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 numeric SOSes produced by the current fixed precision semi-definite programming (SDP) packages (SeDuMi, SOSTOOLS, YALMIP) are usually too coarse to allow successful projection to exact SOSes via Maple 11's exact linear algebra. Therefore, before projection we refine the SOSes by rank-preserving Newton iteration. For smaller problems the starting SOSes for Newton can be guessed without SDP ("SDP-free SOS"), but for larger inputs we additionally appeal to sparsity techniques in our SDP formulation.}, booktitle={Proceedings of the twenty-first international symposium on Symbolic and algebraic computation - ISSAC '08}, publisher={ACM Press}, author={Kaltofen, Erich and Li, Bin and Yang, Zhengfeng and Zhi, Lihong}, year={2008} }
@inproceedings{kaltofen_koiran_2008, title={Expressing a fraction of two determinants as a determinant}, ISBN={9781595939043}, url={http://dx.doi.org/10.1145/1390768.1390790}, DOI={10.1145/1390768.1390790}, abstractNote={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.
Additionally, we show that divisions can be removed from formulas that compute polynomials in the input variables over a sufficiently large field within polynomial formula size growth.}, booktitle={Proceedings of the twenty-first international symposium on Symbolic and algebraic computation - ISSAC '08}, publisher={ACM Press}, author={Kaltofen, Erich and Koiran, Pascal}, year={2008} }
@article{borwein_kaltofen_mossinghoff_2007, title={Irreducible polynomials and barker sequences}, volume={41}, ISSN={1932-2240}, url={http://dx.doi.org/10.1145/1358183.1358185}, DOI={10.1145/1358183.1358185}, abstractNote={
A
Barker sequence
is a finite sequence
a
o
, ...,
a
n
-1
, each term ±1, for which every sum Σ
i
a
i
a
i
+k
with 0 <
k
<
n
is either 0, 1, or -- 1. It is widely conjectured that no Barker sequences of length
n
> 13 exist, and this conjecture has been verified for the case when
n
is odd. We show that in this case the problem can in fact be reduced to a question of irreducibility for a certain family of univariate polynomials: No Barker sequence of length 2
m
+ 1 exists if a particular integer polynomial of degree 4
m
is irreducible over Q. A proof of irreducibility for this family would thus provide a short, alternative proof that long Barker sequences of odd length do not exist. However, we also prove that the polynomials in question are always reducible modulo
p
, for every prime
p
.
}, number={4}, journal={ACM Communications in Computer Algebra}, publisher={Association for Computing Machinery (ACM)}, author={Borwein, Peter and Kaltofen, Erich and Mossinghoff, Michael J.}, year={2007}, month={Dec}, pages={118} }
@inproceedings{kaltofen_li_sivaramakrishnan_yang_zhi_2007, place={New York, NY}, title={Lower bounds for approximate factorizations via semidefinite programming}, ISBN={9781595937445}, booktitle={Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation (SNC '07)}, publisher={ACM Press}, author={Kaltofen, Erich and Li, Bin and Sivaramakrishnan, Kartik and Yang, Zhengfeng and Zhi, Lihong}, editor={Verschelde, Jan and Watt, Stephen M.Editors}, year={2007}, pages={203–204} }
@inproceedings{kaltofen_yang_2007, title={On exact and approximate interpolation of sparse rational functions}, ISBN={9781595937438}, DOI={10.1145/1277548.1277577}, abstractNote={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.}, booktitle={ISSAC 2007: International Symposium for Symbolic and Algebraic Computation: Proceedings}, publisher={New York: ACM Press}, author={Kaltofen, E. and Yang, Z.-F.}, year={2007} }
@inproceedings{kaltofen_yang_zhi_2007, title={On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms}, ISBN={9781595937445}, booktitle={International Workshop on Symbolic-Numeric Computation: Proceedings}, publisher={New York: ACM Press}, author={Kaltofen, E. and Yang, Z.-F. and Zhi, L.-H.}, year={2007} }
@inbook{kaltofen_yang_zhi_2007, title={Structured Low Rank Approximation of a Sylvester Matrix}, ISBN={9783764379834}, url={http://dx.doi.org/10.1007/978-3-7643-7984-1_5}, DOI={10.1007/978-3-7643-7984-1_5}, abstractNote={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 Sylvester matrix of lower rank whose entries are near the corresponding entries of that input matrix. We solve the approximate GCD problem by a new method based on structured total least norm (STLN) algorithms, in our case for matrices with Sylvester structure. We present iterative algorithms that compute an approximate GCD and that can certify an approximate ∈-GCD when a tolerance ∈ is given on input. Each single iteration is carried out with a number of floating point operations that is of cubic order in the input degrees. We also demonstrate the practical performance of our algorithms on a diverse set of univariate pairs of polynomials.}, booktitle={Trends in Mathematics}, publisher={Birkhäuser Basel}, author={Kaltofen, Erich and Yang, Zhengfeng and Zhi, Lihong}, year={2007}, month={Jun}, pages={69–83} }
@inproceedings{kaltofen_yang_zhi_2006, title={Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials}, ISBN={1595932763}, url={http://dx.doi.org/10.1145/1145768.1145799}, DOI={10.1145/1145768.1145799}, abstractNote={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.}, booktitle={Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06}, publisher={ACM Press}, author={Kaltofen, Erich and Yang, Zhengfeng and Zhi, Lihong}, year={2006} }
@inproceedings{decker_dewar_kaltofen_watt_2006, place={Germany}, title={Challenges in Symbolic Computation Software, number 06271}, booktitle={Dagstuhl Seminar Proceedings}, publisher={Schloss Dagstuhl}, year={2006} }
@inproceedings{kaltofen_koiran_2006, title={Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields}, ISBN={1595932763}, url={http://dx.doi.org/10.1145/1145768.1145798}, DOI={10.1145/1145768.1145798}, abstractNote={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.}, booktitle={Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06}, publisher={ACM Press}, author={Kaltofen, Erich and Koiran, Pascal}, year={2006} }
@inproceedings{kaltofen_zhi_2006, title={Hybrid symbolic-numeric computation}, ISBN={1595932763}, url={http://dx.doi.org/10.1145/1145768.1145775}, DOI={10.1145/1145768.1145775}, abstractNote={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.}, booktitle={Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06}, publisher={ACM Press}, author={Kaltofen, Erich and Zhi, Lihong}, year={2006} }
@inbook{kaltofen_yui_2005, place={Berlin, Heidelberg}, series={Lecture Notes in Computer Science}, title={Explicit construction of the hilbert class fields of imaginary quadratic fields with class numbers 7 and 11}, ISBN={354013350X}, url={http://dx.doi.org/10.1007/bfb0032853}, DOI={10.1007/bfb0032853}, booktitle={EUROSAM 84}, publisher={Springer-Verlag}, author={Kaltofen, Erich and Yui, Noriko}, editor={Fitch, J.Editor}, year={2005}, month={Dec}, pages={310–320}, collection={Lecture Notes in Computer Science} }
@inproceedings{kaltofen_morozov_yuhasz_2005, title={Generic matrix multiplication and memory management in linBox}, ISBN={1595930957}, url={http://dx.doi.org/10.1145/1073884.1073915}, DOI={10.1145/1073884.1073915}, abstractNote={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.}, booktitle={Proceedings of the 2005 international symposium on Symbolic and algebraic computation - ISSAC '05}, publisher={ACM Press}, author={Kaltofen, Erich and Morozov, Dmitriy and Yuhasz, George}, year={2005} }
@article{kaltofen_villard_2005, title={On the complexity of computing determinants}, volume={13}, ISSN={["1420-8954"]}, DOI={10.1007/s00037-004-0185-3}, abstractNote={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 form and Smith normal form of a dense n × n matrix A with integer entries in $$\left( {n^{3.2} \log \left\| A \right\|} \right)^{1 + o(1)} $$ and $$\left( {n^{2.697263} \log \left\| A \right\|} \right)^{1 + o(1)} $$ bit operations; here $$\left\| A \right\|$$ denotes the largest entry in absolute value and the exponent adjustment by “+o(1)” captures additional factors $$C_1 (\log n)^{C_2 } \left( {\log \log \left\| A \right\|} \right)^{C_3 } $$ for positive real constants C1, C2, C3. The bit complexity $$\left( {n^{3.2} \log \left\| A \right\|} \right)^{1 + o(1)} $$ results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n3.2+o(1) and O(n2.697263) ring additions, subtractions and multiplications.}, number={3-4}, journal={COMPUTATIONAL COMPLEXITY}, author={Kaltofen, E and Villard, G}, year={2005}, month={Feb}, pages={91–130} }
@inproceedings{kaltofen_koiran_2005, title={On the complexity of factoring bivariate supersparse (Lacunary) polynomials}, ISBN={1595930957}, url={http://dx.doi.org/10.1145/1073884.1073914}, DOI={10.1145/1073884.1073914}, abstractNote={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.}, booktitle={Proceedings of the 2005 international symposium on Symbolic and algebraic computation - ISSAC '05}, publisher={ACM Press}, author={Kaltofen, Erich and Koiran, Pascal}, year={2005} }
@inproceedings{gao_kaltofen_may_yang_zhi_2004, title={Approximate factorization of multivariate polynomials via differential equations}, ISBN={158113827X}, url={http://dx.doi.org/10.1145/1005285.1005311}, DOI={10.1145/1005285.1005311}, abstractNote={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).}, booktitle={Proceedings of the 2004 international symposium on Symbolic and algebraic computation - ISSAC '04}, publisher={ACM Press}, author={Gao, Shuhong and Kaltofen, Erich and May, John and Yang, Zhengfeng and Zhi, Lihong}, year={2004} }
@article{kaltofen_villard_2004, title={Computing the sign or the value of the determinant of an integer matrix, a complexity survey}, volume={162}, ISSN={["1879-1778"]}, DOI={10.1016/j.cam.2003.08.019}, abstractNote={Computation of the sign of the determinant of a matrix and the determinant itself is a challenge for both numerical and exact methods. We survey the complexity of existing methods to solve these problems when the input is an n×n matrix A with integer entries. We study the bit-complexities of the algorithms asymptotically in n and the norm of A. Existing approaches rely on numerical approximate computations, on exact computations, or on both types of arithmetic in combination.}, number={1}, journal={JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS}, author={Kaltofen, E and Villard, G}, year={2004}, month={Jan}, pages={133–146} }
@article{gao_kaltofen_lauder_2004, title={Deterministic distinct-degree factorization of polynomials over finite fields}, volume={38}, ISSN={["0747-7171"]}, DOI={10.1016/j.jsc.2004.05.004}, abstractNote={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 irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987.}, number={6}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Gao, SH and Kaltofen, E and Lauder, AGB}, year={2004}, month={Dec}, pages={1461–1470} }
@article{eberly_kaltofen_2004, title={Early termination in Shoup's algorithm for the minimum polynomial of an algebraic}, author={Eberly, Wayne and Kaltofen, Erich}, year={2004} }
@inbook{kaltofen_2003, place={Heidelberg, Germany}, title={Absolute factorization of polynomials}, booktitle={Computer Algebra Handbook}, publisher={Springer Verlag}, author={Kaltofen, E.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003}, pages={26} }
@article{giesbrecht_kaltofen_lee_2003, title={Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases}, volume={36}, ISSN={["0747-7171"]}, DOI={10.1016/S0747-7171(03)00087-7}, abstractNote={We give a new class of algorithms for computing sparsest shifts of a given polynomial. Our algorithms are based on the early termination version of sparse interpolation algorithms: for a symbolic set of interpolation points, a sparsest shift must be a root of the first possible zero discrepancy that can be used as the early termination test. Through reformulating as multivariate shifts in a designated set, our algorithms can compute the sparsest shifts that simultaneously minimize the terms of a given set of polynomials. Our algorithms can also be applied to the Pochhammer and Chebyshev bases for the polynomials, and potentially to other bases as well. For a given univariate polynomial, we give a lower bound for the optimal sparsity. The efficiency of our algorithms can be further improved by imposing such a bound and pruning the highest degree terms.}, number={3-4}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Giesbrecht, M and Kaltofen, E and Lee, WS}, year={2003}, pages={401–424} }
@book{grabmeier_weispfenning_2003, place={Heidelberg, Germany}, title={Computer Algebra Handbook}, publisher={Springer Verlag}, author={Grabmeier, J. and Weispfenning, V.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003} }
@inbook{kaltofen_weispfenning_2003, place={Heidelberg, Germany}, title={Computer algebra - impact on research}, booktitle={Computer Algebra Handbook}, publisher={Springer Verlag}, author={Kaltofen, E. and Weispfenning, V.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003}, pages={4–6} }
@book{computer algebra handbook foundations, applications, systems_2003, DOI={10.1007/978-3-540-72122-2_20}, publisher={Berlin ;|aNew York: Springer}, year={2003} }
@article{kaltofen_lee_2003, title={Early termination in sparse interpolation algorithms}, volume={36}, ISSN={["0747-7171"]}, DOI={10.1016/S0747-7171(03)00088-9}, abstractNote={A probabilistic strategy, early termination, enables different interpolation algorithms to adapt to the degree or the number of terms in the target polynomial when neither is supplied in the input. In addition to dense algorithms, we implement this strategy in sparse interpolation algorithms. Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms. The racing algorithms can be embedded as the univariate interpolation substep within Zippel’s multivariate method. In addition, we experimentally verify some heuristics of early termination, which make use of thresholds and post-verification.}, number={3-4}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, E and Lee, ES}, year={2003}, pages={365–400} }
@inbook{kaltofen_2003, place={Heidelberg, Germany}, title={FoxBox and other blackbox systems}, booktitle={Computer Algebra Handbook}, publisher={Springer Verlag}, author={Kaltofen, E.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003}, pages={383–385} }
@inbook{corless_kaltofen_watt_2003, place={Heidelberg, Germany}, title={Hybrid methods}, booktitle={Computer Algebra Handbook}, publisher={Springer Verlag}, author={Corless, M. and Kaltofen, E. and Watt, S. M.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003}, pages={112–125} }
@inbook{kaltofen_saunders_2003, place={Heidelberg, Germany}, title={Linear systems}, booktitle={Computer algebra handbook: foundations, applications, systems}, publisher={Springer Verlag}, author={Kaltofen, E. and Saunders, B. D.}, editor={Grabmeier, J. and Kaltofen, E. and Weispfenning, V.Editors}, year={2003}, pages={36–38} }
@inproceedings{kaltofen_may_2003, title={On approximate irreducibility of polynomials in several variables}, ISBN={1581136412}, url={http://dx.doi.org/10.1145/860854.860893}, DOI={10.1145/860854.860893}, abstractNote={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.}, booktitle={Proceedings of the 2003 international symposium on Symbolic and algebraic computation - ISSAC '03}, publisher={ACM Press}, author={Kaltofen, Erich and May, John}, year={2003} }
@inproceedings{kaltofen_2003, title={Polynomial factorization}, ISBN={1581136412}, url={http://dx.doi.org/10.1145/860854.860857}, DOI={10.1145/860854.860857}, abstractNote={The problem of factoring a polynomial in a single or severalvariables over a finite field, the rational numbers or the complexnumbers is one of the success stories in the discipline of symboliccomputation. In the early 1960s implementors investigated theconstructive methods known from classical algebra books, but--withthe exception of Gauss's distinct degree factorizationalgorithm--found the algorithms quite inefficient in practice [16].The contributions in algorithmic techniques that have been madeover the next 40 years are truly a hallmark of symbolic computationresearch.
The early pioneers, Berlekamp, Musser, Wang, Weinberger,Zassenhaus and others applied new ideas like randomization, thateven before the now famous algorithms for primality testing byRabin and Strassen, and like generic programming with coefficientdomains as abstract data classes, and they introduced the powerfulHensel lifting lemma to computer algebra. We note that whilede-randomization for integer primality testing has beenaccomplished recently [1], the same remains open for the problem ofcomputing a root of a polynomial modulo a large prime [12, ResearchProblem 14.48].
Polynomial-time complexity for rational coefficients wasestablished in the early 1980s by the now-famous lattice basisreduction algorithm of A. Lenstra, H. W. Lenstra, Jr., and L.Lovász. The case of many variables first became anapplication of the DeMillo and Lipton/Schwartz/Zippel lemma [30]and then triggered a fundamental generalization from the standardsparse (distributed) representation of polynomials to the one bystraight line and black box programs [11, 17, 19]. Effectiveversions of the Hilbert irreducibility theorem are needed for theprobabilistic analysis, which serendipitously later have alsoplayed a role in the PCP characterization of NP[2]. Unlike many other problems in commutative algebra andalgebraic geometry, such as algebraic system solving, thepolynomial factoring problem is of probabilistic polynomial-timecomplexity in the number of variables.
Complex coefficients in multivariate factors can be representedeither by exact algebraic numbers or by imprecise floating pointnumbers. The latter formulation is a cornerstone in the newcomputer algebra subject of SNAP (Symbolic-Numeric Algorthms forPolynomials) (see, e.g., [4]). The approaches for both exact andimprecise coefficients are manifold, including Ruppert's partialdifferential equations [26, 27, 6, 10] and Gao's and Lauder'sfar-reaching generalization of Eisenstein's criterion in themultivariate case to Newton polytope decomposition [8, 9]. Thecurrently best algorithms were all discovered recently within thepast ten years.
The baby steps/giant steps technique and fast distinct and equaldegree factorization implementations have, at last, yielded in themid 1990s theoretical and practical improvements over the originalunivariate Berlekamp algorithm for coefficients in finite fields[13, 29, 18, 3]. The average time analysis for selected algorithmsis also completed [5]. For bivariate polynomials over finitefields, surprisingly Gröbner basis techniques are useful inpractice [23].
New polynomial-time complexity results are the computation oflow degree factors of very high degree sparse (lacunary)polynomials by H. W. Lenstra, Jr. [20, 21], and the deterministicdistinct degree factorization for multivariate polynomials overlarge finite fields [7]. However, many problems with high degreepolynomials over large finite fields in sparse or straight lineprogram representations, such as computing a root modulo a largeprime, are not known to be in random polynomial time or NP-hard(cf. [24, 25, 15]).
Finally, in 2000 Mark van Hoeij [14] reintroduced lattice basisreduction, now in the Berlekamp-Zassenhaus algorithm, to conquerthe hard-to-factor Swinnerton-Dyer polynomials in practice. Sasakiin 1993 had already hinted of the used approach [28].
In my talk I will discuss a selection of the highlights, stateremaining open problems, and give some applications including anunusual one due to Moni Naor [22].}, booktitle={Proceedings of the 2003 international symposium on Symbolic and algebraic computation - ISSAC '03}, publisher={ACM Press}, author={Kaltofen, Erich}, year={2003} }
@inproceedings{kaltofen_mclean_norris_2002, place={Waterloo, Canada}, title={'Using Maple to grade Maple' assessment software from North Carolina State University}, booktitle={Proceedings 2002 Maple Workshop}, publisher={Waterloo Maple Inc. With Dmitriy Morozov, John May and William Turner}, author={Kaltofen, Erich and McLean, Michael and Norris, Larry}, year={2002} }
@inproceedings{giesbrecht_kaltofen_lee_2002, place={New York}, title={Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm}, ISBN={1581134843 9781581134841}, url={http://dx.doi.org/10.1145/780506.780519}, DOI={10.1145/780506.780519}, abstractNote={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.}, booktitle={Proceedings of the 2002 international symposium on Symbolic and algebraic computation - ISSAC '02}, publisher={ACM Press}, author={Giesbrecht, Mark and Kaltofen, Erich and Lee, Wen-shin}, year={2002} }
@inproceedings{kaltofen_2002, title={An output-sensitive variant of the baby steps/giant steps determinant algorithm}, ISBN={1581134843}, url={http://dx.doi.org/10.1145/780506.780524}, DOI={10.1145/780506.780524}, abstractNote={In the first half of 2000, two new algorithms were discovered for the efficient computation of the determinant of a (dense) matrix with integer entries. Suppose that the dimension of the matrix is n x n and that the maximum bit length of all entries is b. The algorithm by [10] requires (n3.5b2.5)1+o(1) fixed precision, that is, bit operations. Here and in the following we use the exponent "+o(1)" to capture missing polylogarithmic factors O((log n)C1(log b)C2), where C1, C2 are constants ("soft-O"). As it has turned out an algorithm in [15], which in turn is based on one by [31] and which uses the baby steps/giant steps algorithm design technique, can be adapted to the dense integer matrix determinant problem and then has bit complexity (n3.5b)1+o(1) [20, Section 2]. Both algorithms use randomization and the algorithm in [10] is Monte Carlo--always fast and probably correct--and the one in [20] is Las Vegas--always correct and probably fast. Both algorithms can be speeded by asymptotically fast subcubic matrix multiplication algorithms à la Strassen [8, 7, 14]. By blocking [6, 16, 29, 30] the baby steps/giant steps algorithm can be further improved, which yields the currently fastest known algorithms [20, Section 3] of bit complexity (n3+1/3b)1+o(1), that without subcubic matrix multiplication and without the FFT-based polynomial "half" GCD procedures à la Knuth [23; 2, Chapter 8], and of bit complexity n2.698b1+o(1) with subcubic matrix multiplication and FFT-based polynomial GCD procedures.}, booktitle={Proceedings of the 2002 international symposium on Symbolic and algebraic computation - ISSAC '02}, publisher={ACM Press}, author={Kaltofen, Erich}, year={2002} }
@article{chen_eberly_kaltofen_saunders_turner_villard_2002, title={Efficient matrix preconditioners for black box linear algebra}, volume={343}, ISSN={["0024-3795"]}, DOI={10.1016/S0024-3795(01)00472-4}, abstractNote={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 desired result. Here good preconditioners will be used to ensure geometrical/algebraic properties on matrices, rather than numerical ones, so we do not address a condition number. We offer a review of problems for which (algebraic) preconditioning is used, provide a bestiary of preconditioning problems, and discuss several preconditioner types to solve these problems. We present new conditioners, including conditioners to preserve low displacement rank for Toeplitz-like matrices. We also provide new analyses of preconditioner performance and results on the relations among preconditioning problems and with linear algebra problems. Thus, improvements are offered for the efficiency and applicability of preconditioners. The focus is on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields.}, journal={LINEAR ALGEBRA AND ITS APPLICATIONS}, author={Chen, L and Eberly, W and Kaltofen, E and Saunders, BD and Turner, WJ and Villard, G}, year={2002}, month={Mar}, pages={119–146} }
@inproceedings{dumas_gautier_giesbrecht_giorgi_hovinen_kaltofen_saunders_turner_villard_2002, title={LINBOX: A GENERIC LIBRARY FOR EXACT LINEAR ALGEBRA}, ISBN={9789812380487 9789812777171}, url={http://dx.doi.org/10.1142/9789812777171_0005}, DOI={10.1142/9789812777171_0005}, abstractNote={Black box techniques [12] are enabling exact linear algebra computations of a scale well beyond anything previously possible. The development of new and interesting algorithms has proceeded apace for the past two decades. It is time for the dissemination of these algorithms in an easily used software library so that the mathematical community may readily take advantage of their power. LinBox is that library. In this paper, we describe the design of this generic library, sketch its current range of capabilities, and give several examples of its use. The examples include a solution of Trefethen’s “Hundred Digit Challenge” problem #7 [14] and the computation of all the homology groups of simplicial complexes using the Smith normal form [8]. Exact black box methods are currently successful on sparse matrices with hundreds of thousands of rows and columns and having several million nonzero entries. The main reason large problems can be solved by black box methods is that they require much less memory in general than traditional eliminationbased methods do. This fact is widely used in the numerical computation area. We refer for instance to the templates for linear system solution and eigenvalue problems [2,1]. This has also led the computer algebra community to a considerable interest in black box methods. Since Wiedemann’s seminal paper [16], many developments have been proposed especially to adapt Krylov or Lanczos methods to fast exact algorithms. We refer to [5] and references therein for a review of problems and solutions. LinBox supplies efficient black box solutions for a variety of problems including linear equations and matrix normal forms with the guiding design principle of re-usability. The most essential and driving design criterion for LinBox is that it is generic with respect to the domain of computation. This is because there are many and various representations of finite fields each of which is advantageous to use for some algorithm under some circumstance. The integral and rational number capabilities depend heavily on modular}, booktitle={Mathematical Software}, publisher={WORLD SCIENTIFIC}, author={Dumas, J. G. and Gautier, T. and Giesbrecht, M. and Giorgi, P. and Hovinen, B. and Kaltofen, E. and Saunders, B. D. and Turner, W. J. and Villard, G.}, year={2002}, month={Jul} }
@inproceedings{kaltofen_2001, title={Algorithms for sparse and black box matrices over finite fields}, author={Kaltofen, E.}, year={2001}, month={May} }
@misc{kaltofen_2000, title={Challenges of symbolic computation: My favorite open problems}, volume={29}, ISSN={["1095-855X"]}, DOI={10.1006/jsco.2000.0370}, abstractNote={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 lattice basis reduction, hypergeometric summation algorithms, etc. From the beginning in the early 1960s, it has been the tradition of our discipline to create software that makes our ideas readily available to scientists, engineers, and educators: SAC-1, Reduce, Macsyma, etc. The commercial viability of our system products is proven by Maple and Mathematica. Today?s user communities of symbolic computation systems are diverse: educators, engineers, stock market analysts, etc. The mathematics and computer science in the design and implementation of our algorithms are sophisticated. The research challenges in symbolic computation at the close of the twentieth century are formidable. I state my favorite eight open problems in symbolic computation. They range from problems in symbolic/numeric computing, symbolic algorithm synthesis, to system component construction. I have worked on seven of my problems and borrowed one from George Collins. I present background to each of my problems and a clear-cut test that evaluates whether a proposed attack has solved one of my problems. An additional ninth open problem by Rob Corless and David Jeffrey on complex function semantics is given in an appendix.}, number={6}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, E}, year={2000}, month={Jun}, pages={891–919} }
@inproceedings{kaltofen_lee_lobo_2000, title={Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm}, ISBN={1581132182}, url={http://dx.doi.org/10.1145/345542.345629}, DOI={10.1145/345542.345629}, abstractNote={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}, booktitle={Proceedings of the 2000 international symposium on Symbolic and algebraic computation symbolic and algebraic computation - ISSAC '00}, publisher={ACM Press}, author={Kaltofen, Erich and Lee, Wen-shin and Lobo, Austin A.}, year={2000} }
@article{kaltofen_lobo_1999, title={Distributed matrix-free solution of large sparse linear systems over finite fields}, volume={24}, ISSN={["0178-4617"]}, DOI={10.1007/PL00008266}, number={3-4}, journal={ALGORITHMICA}, author={Kaltofen, E and Lobo, A}, year={1999}, pages={331–348} }
@article{hong_kaltofen_singer_1999, title={East Coast Computer Algebra Day '99 (April 24, 1999): Abstracts of invited talks and presented posters}, volume={33}, DOI={10.1145/334714.570085}, abstractNote={s of Invited Talks and Presented Posters* Hoon Hong Erich Kaltofen and Michael Singer (Editors) N o r t h C a r o l i n a S t a t e U n i v e r s i t y M a t h e m a t i c s D e p a r t m e n t , B o x 8205 R a l e i g h , N . C . 27695-8205 U S A URL: www.math, ncsu. edu 1 I n v i t e d T a l k s T h r e e P i e c e s o f ( C o m p u t a t i o n a l ) N u m b e r T h e o r y and a Little Phi losophy}, number={2}, journal={Association for Computing Machinery SIGSAM Bulletin}, year={1999}, month={Jun}, pages={43–52} }
@inproceedings{hitz_kaltofen_lakshman_1999, title={Efficient algorithms for computing the nearest polynomial with a real root and related problems}, ISBN={1581130732}, url={http://dx.doi.org/10.1145/309831.309937}, DOI={10.1145/309831.309937}, abstractNote={We present three new algorithms in the general area of input-sensitivity analysis: a problem formulation, possibly with floating point coefficients, lacks an expected property because the inputs are slightly perturbed. A task is to efficiently compute the nearest problem that has the desired property. Nearness to the desired property can lead to problems for numerical algorithms: for example, an almost singular linear system cannot be solved by classical numerical techniques. In such case one can approach the problem of locating the nearest problem with the desired property by symbolic computation techniques, for instance, by exact arithmetic. Our three properties are:}, booktitle={Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99}, publisher={ACM Press}, author={Hitz, Markus A. and Kaltofen, Erich and Lakshman, Y. N.}, year={1999} }
@inproceedings{kaltofen_monagan_1999, title={On the genericity of the modular polynomial GCD algorithm}, ISBN={1581130732}, url={http://dx.doi.org/10.1145/309831.309861}, DOI={10.1145/309831.309861}, abstractNote={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. Details for the parameterization and generic Maple code are given. Applying this generic algorithm to a GCD problem in Z/(p)[t][x] where p is small yields an improved asymptotic performance over the usual approach, and a very practical algorithm for polynomials over small finite fields.}, booktitle={Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99}, publisher={ACM Press}, author={Kaltofen, Erich and Monagan, Michael B.}, year={1999} }
@inproceedings{bernardin_char_kaltofen_1999, title={Symbolic computation in Java}, ISBN={1581130732}, url={http://dx.doi.org/10.1145/309831.309946}, DOI={10.1145/309831.309946}, abstractNote={Java, first developed as a programming interface for web browsers, is being pushed by a consortium of companies as a high level programming language for general programming. Sun Microsystems provides, in addition to a compiler into byte code for an interpreter (the Java virtual machine), a multitude of libraries, most notably an object hierarchy for building graphical user interfaces: the Abstract 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 Internet documents as applets. Java defines a standard framework for multi-threaded execution and for message passing via serialization and socket/datagram protocols. Java assists component composition in two ways. Java objects can discover how to invoke other Java objects at run-time through a process called reflection. Java also supports programming conventions (collectively referred to as “Java Beans”) for event-driven inter-component operation. The two together allow tools such as Java Studio [26] to provide convenient visual programming methods of connecting up Java software components. In short, Java is being vigorously developed and we ask the natural question whether Java is suited for symbolic computation and whether our discipline should take advantage of the plethora of freely available software. This article discusses Java as a symbolic computation development tool, expanding on the pioneering efforts of other researchers [39, 9]. We investigate if Java can compete with C++, or Maple/Mathematica/Axiom for efficient}, booktitle={Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99}, publisher={ACM Press}, author={Bernardin, Laurent and Char, Bruce and Kaltofen, Erich}, year={1999} }
@inbook{díaz_emiris_kaltofen_pan_1998, title={Algebraic Algorithms}, ISBN={9780849326493 9781420049503}, ISSN={2154-4034}, url={http://dx.doi.org/10.1201/9781420049503-c17}, DOI={10.1201/9781420049503-c17}, abstractNote={This is a preliminary version of a Chapter on Algebraic Algorithms in the upcoming Computing Handbook Set Computer Science (Volume I), CRC Press/Taylor and Francis Group. Algebraic algorithms deal with numbers, vectors, matrices, polynomials, formal power series, exponential and differential polynomials, rational functions, algebraic sets, curves and surfaces. In this vast area, manipulation with matrices and polynomials is most fundamental for modern computations in Sciences, Engineering, and Signal and Image Processing. They include the solution of a polynomial equation and linear and polynomial systems of equations, univariate and multivariate polynomial evaluation, interpolation, factorization and decompositions, rational interpolation, computing matrix factorization and decompositions (which in turn include various triangular and orthogonal factorizations such as LU, PLU, QR, QRP, QLP, CS, LR, Cholesky factorizations and eigenvalue and singular value decompositions), computation of the matrix characteristic and minimal polynomials, determinants, Smith and Frobenius normal forms, ranks, and (generalized) inverses, univariate and multivariate polynomial resultants, Newton’s polytopes, greatest common divisors, and least common multiples as well as manipulation with truncated series and algebraic sets. Such problems can be solved based on the error-free symbolic computations with infinite precision. The computer library GMP and computer algebra}, booktitle={Algorithms and Theory of Computation Handbook}, publisher={CRC Press}, author={Díaz, Angel and Emiris, Ioannis and Kaltofen, Erich and Pan, Victor}, year={1998}, month={Nov} }
@inproceedings{hitz_kaltofen_1998, title={Efficient algorithms for computing the nearest polynomial with constrained roots}, ISBN={1581130023}, url={http://dx.doi.org/10.1145/281508.281624}, DOI={10.1145/281508.281624}, abstractNote={The location of polynomial roots is sensitive to perturbations of the coefficients. Continuous changes of the coefficients of a polynomial move the roots continuously. We consider the problem of finding the minimal perturbations to the coefficients to move one or several roots to given loci. We measure minimality in the Euclidean distance to the coefficient vector, as well as the maximal coefficient-wise change in absolute value (infinity norm), and in the Manhattan norm ($l\sp1$-norm). In the Euclidean norm the computational task reduces to a least squares problem, in the infinity norm and the $l\sp1$-norm it can be formulated as a linear program.
We can derive symbolic solutions in closed form for the Euclidean norm in the case of complex coefficients and a single complex root. Our new result is a formula for the minimum change in the infinity norm for the case of real coefficients and a single real root. Based on the principle of parametric minimization we develop hybrid symbolic-numeric algorithms to constrain one root of a complex or real polynomial to a curve in the complex plane.
As an application to robust control, we give a polynomial-time algorithm to compute the radius of stability in the Euclidean norm for a variety of stability domains.}, booktitle={Proceedings of the 1998 international symposium on Symbolic and algebraic computation - ISSAC '98}, publisher={ACM Press}, author={Hitz, Markus A. and Kaltofen, Erich}, year={1998} }
@inproceedings{díaz_kaltofen_1998, title={FOXBOX}, ISBN={1581130023}, url={http://dx.doi.org/10.1145/281508.281538}, DOI={10.1145/281508.281538}, abstractNote={The dreaded phenomenon of expression swell in symbolic computation can be palliated by adopting implicit representations for symbolic objects, such as straight-line programs or so-called black box representations. In the latter, each expression is a symbolic object, more specifically, a computer program with a set of statically initialized data, which takes as input a value for each variable and then produces the value of the symbolic object it represents at the specified point.
In this thesis we introduce F sc OXB sc OX, a software package that puts in practice the black box representation of symbolic objects and provides algorithms for performing the symbolic calculus with such representations. Improved versions of the algorithms found in Kaltofen and Trager (Journal of Symbolic Computing, vol. 9, nr. 3, p. 311 (1990)) and Kaltofen and Diaz (International Symposium on Symbolic and Algebraic Computation '95,) p. 232) are discussed. Also we describe an interpolation scheme based on a Zippel's algorithm (Journal of Symbolic Computing, vol. 9, nr. 3, p. 375 (1990)) that optimizes the number of required black box evaluations.
The design of F sc OXB sc OX is intended to demonstrate how plug-in software components can be employed for generally used symbolic systems. Our implementation incorporates data types parameterized by arbitrary coefficient domains and generic algorithms. By providing a mechanism for interfacing to general purpose computer algebra systems, we broaden F sc OXB scOX's applicability. Furthermore we provide a distribution mechanism that allows for parallel and distributed execution of F sc OXB sc OX programs independent of the underlying parallel architecture.
Finally, we present the results of several challenge problems which exercise our F sc OXB sc OX library and represent the first symbolic solutions of such problems.}, booktitle={Proceedings of the 1998 international symposium on Symbolic and algebraic computation - ISSAC '98}, publisher={ACM Press}, author={Díaz, Angel and Kaltofen, Erich}, year={1998} }
@article{kaltofen_shoup_1998, title={Subquadratic-time factoring of polynomials over finite fields}, volume={67}, ISSN={["0025-5718"]}, DOI={10.1090/S0025-5718-98-00944-2}, abstractNote={New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n n over a finite field of constant cardinality in time O ( n 1.815 ) O(n^{1.815}) . Previous algorithms required time Θ ( n 2 + o ( 1 ) ) \Theta (n^{2+o(1)}) . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n n over the finite field F q {\mathbb F}_q with q q elements, the algorithms use O ( n 1.815 log q ) O(n^{1.815} \log q) arithmetic operations in F q {\mathbb F}_q . The new “baby step/giant step” techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.}, number={223}, journal={MATHEMATICS OF COMPUTATION}, author={Kaltofen, E and Shoup, V}, year={1998}, month={Jul}, pages={1179–1197} }
@inbook{díaz_kaltofen_pan_1997, place={Boca Raton, Florida}, title={Algebraic algorithms}, ISBN={9780849329098}, booktitle={The computer science and engineering handbook}, publisher={CRC Press}, author={Díaz, A. and Kaltofen, E. and Pan, V.}, editor={Tucker, A.B.Editor}, year={1997}, pages={226–248} }
@inproceedings{kaltofen_shoup_1997, title={Fast polynomial factorization over high algebraic extensions of finite fields}, ISBN={0897918754}, url={http://dx.doi.org/10.1145/258726.258777}, DOI={10.1145/258726.258777}, abstractNote={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, where a > 0 is constant, these algorithms are asymptotically faster than previous known algorithms, the fastest of which required time Ω(n(log q)), or Ω(n) in this case, which corresponds to the cost of computing x modulo an n degree polynomial. The new algorithms factor an arbitrary polynomial in time O(n+n). 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). In particular, one may test a polynomial for irreducibility in O(n) bit operations. These results generalize to the case where q = p, where p is a small prime number relative to q.}, booktitle={Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC '97}, publisher={ACM Press}, author={Kaltofen, Erich and Shoup, Victor}, year={1997} }
@inproceedings{eberly_kaltofen_1997, title={On randomized Lanczos algorithms}, ISBN={0897918754}, url={http://dx.doi.org/10.1145/258726.258776}, DOI={10.1145/258726.258776}, abstractNote={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.}, booktitle={Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC '97}, publisher={ACM Press}, author={Eberly, Wayne and Kaltofen, Erich}, year={1997} }
@book{hong_kaltofen_hitz_1997, place={New York}, title={PASCO '97: Proceedings of the second international symposium on Parallel symbolic computation}, ISBN={0897919513 9780897919517}, url={http://dx.doi.org/10.1145/266670}, DOI={10.1145/266670}, publisher={ACM Press}, year={1997} }
@article{kaltofen_1997, title={Teaching computational abstract algebra}, volume={23}, ISSN={["0747-7171"]}, DOI={10.1006/jsco.1996.0104}, abstractNote={Abstract 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 the didactical use of the corresponding Mathematica packages, as well as draw conclusions for future such courses from the students' comments and our own experience.}, number={5-6}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, author={Kaltofen, E}, year={1997}, pages={503–515} }
@inproceedings{kaltofen_1996, place={Sophia Antipolis, France}, title={Blocked iterative sparse linear system solvers for finite fields}, booktitle={Proceedings of the Symposium of Parallel Computing Solving Large Scale Irregular Applications (Stratagem '96)}, publisher={INRIA}, author={Kaltofen, E.}, editor={Roucairol, C.Editor}, year={1996}, pages={91–95} }
@inproceedings{erlingsson_kaltofen_musser_1996, title={Generic Gram-Schmidt orthogonalization by exact division}, ISBN={0897917960}, url={http://dx.doi.org/10.1145/236869.237085}, DOI={10.1145/236869.237085}, abstractNote={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.}, booktitle={Proceedings of the 1996 international symposium on Symbolic and algebraic computation - ISSAC '96}, publisher={ACM Press}, author={Erlingsson, Úlfar and Kaltofen, Erich and Musser, David}, year={1996} }
@inproceedings{kaltofen_lobo_1996, title={On rank properties of Toeplitz matrices over finite fields}, ISBN={0897917960}, url={http://dx.doi.org/10.1145/236869.237081}, DOI={10.1145/236869.237081}, abstractNote={Out of all the n×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)(1 − 1/q)(1 − (q − 1)/q) has generic rank 0 < 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.}, booktitle={Proceedings of the 1996 international symposium on Symbolic and algebraic computation - ISSAC '96}, publisher={ACM Press}, author={Kaltofen, E. and Lobo, A.}, year={1996} }
@inbook{samadani_kaltofen_1996, title={Prediction Based Task Scheduling in Distributed Computing}, ISBN={9781461359791 9781461523154}, url={http://dx.doi.org/10.1007/978-1-4615-2315-4_30}, DOI={10.1007/978-1-4615-2315-4_30}, booktitle={Languages, Compilers and Run-Time Systems for Scalable Computers}, publisher={Springer US}, author={Samadani, Mehrdad and Kaltofen, Erich}, year={1996}, pages={317–320} }
@article{kaltofen_1995, title={Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems}, volume={64}, ISSN={0025-5718}, url={http://dx.doi.org/10.1090/s0025-5718-1995-1270621-1}, DOI={10.1090/s0025-5718-1995-1270621-1}, abstractNote={By using projections by a block of vectors in place of a single vector it is possible to parallelize the outer loop of iterative methods for solving sparse linear systems. We analyze such a scheme proposed by Coppersmith for Wiedemann’s coordinate recurrence algorithm, which is based in part on the Krylov subspace approach. We prove that by use of certain randomizations on the input system the parallel speed up is roughly by the number of vectors in the blocks when using as many processors. Our analysis is valid for fields of entries that have sufficiently large cardinality. Our analysis also deals with an arising subproblem of solving a singular block Toeplitz system by use of the theory of Toeplitz-like matrices.}, number={210}, journal={Mathematics of Computation}, publisher={American Mathematical Society (AMS)}, author={Kaltofen, Erich}, year={1995}, month={May}, pages={777–777} }
@article{kaltofen_1995, title={Effective Noether Irreducibility Forms and Applications}, volume={50}, ISSN={0022-0000}, url={http://dx.doi.org/10.1006/jcss.1995.1023}, DOI={10.1006/jcss.1995.1023}, abstractNote={Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree. A (multivariate) polynomial over a specific field is said to be absolutely irreducible if it is irreducible over the algebraic closure of its coefficient field. A specific polynomial of a certain degree is absolutely irreducible, if and only if all the corresponding irreducibility forms vanish when evaluated at the coefficients of the specific polynomial. Our forms have much smaller degrees and coefficients than the forms derived originally by Emmy Noether. We can also apply our estimates to derive more effective versions of irreducibility theorems by Ostrowski and Deuring and of the Hilbert irreducibility theorem. We also give an effective estimate on the diameter of the neighborhood of an absolutely irreducible polynomial with respect to the coefficient space in which absolute irreducibility is preserved. Furthermore, we can apply the effective estimates to derive several factorization results in parallel computational complexity theory: we show how to compute arbitrary high precision approximations of the complex factors of a multivariate integral polynomial and how to count the number of absolutely irreducible factors of a multivariate polynomial with coefficients in a rational function field, both in the complexity class NC. The factorization results also extend to the case where the coefficient field is a function field.}, number={2}, journal={Journal of Computer and System Sciences}, publisher={Elsevier BV}, author={Kaltofen, E.}, year={1995}, month={Apr}, pages={274–295} }
@article{hitz_kaltofen_1995, title={Integer division in residue number systems}, volume={44}, ISSN={0018-9340}, url={http://dx.doi.org/10.1109/12.403714}, DOI={10.1109/12.403714}, abstractNote={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. >}, number={8}, journal={IEEE Transactions on Computers}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Hitz, M.A. and Kaltofen, E.}, year={1995}, pages={983–989} }
@inproceedings{díaz_kaltofen_1995, place={New York}, title={On computing greatest common divisors with polynomials given by black boxes for their evaluations}, ISBN={0897916999 9780897916998}, url={http://dx.doi.org/10.1145/220346.220375}, DOI={10.1145/220346.220375}, abstractNote={The black box representation of a multivariate polynomial is a function that takes as input a value for each variable and then produces the value of the polynomial. We revisit the problem of computing the greatest common divisor (GCD) in black box format of several multivariate polynomials that themselves are given by black boxes. To this end an improved version of the algorithm sketched in Kaltofen and Trager [J. Symbolic Comput., vol. 9, nr. 3, p. 311 (1990)] is described. Also the full analysis of the improved algorithm is given. Our algorithm constructs in random polynomial-time a procedure that will evaluate a (cid:12)xed associate of the GCD at an arbitrary point (supplied as its input) in polynomial time. The randomization of the black box construction is of the Monte-Carlo kind, that is with controllably high probability the procedures evaluating the GCD are correct at all input points. Finally, a Maple prototype implementation as well as our plans for developing a subsystem for manipulating multivariate polynomials and rational functions in black box representation are presented.}, booktitle={Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95}, publisher={ACM Press}, author={Díaz, Angel and Kaltofen, Erich}, editor={Levelt, A.H.M.Editor}, year={1995} }
@article{dı́az a._hitz_kaltofen_lobo_valente_1995, title={Process Scheduling in DSC and the Large Sparse Linear Systems Challenge}, volume={19}, ISSN={0747-7171}, url={http://dx.doi.org/10.1006/jsco.1995.1015}, DOI={10.1006/jsco.1995.1015}, abstractNote={New features of our DSC system for distributing a symbolic computation task over a network of processors are described. A new scheduler sends parallel subtasks to those compute nodes that are best suited in handling the added load of CPU usage and memory. Furthermore, a subtask can communicate back to the process that spawned it by a co-routine style calling mechanism. Two large experiments are described in this improved setting. In the first we have implemented an algorithm that can prove a number of more than 1,000 decimal digits prime in about 2 months elapsed time on some 20 computers. In the second a parallel version of a sparse linear system solver is used to compute the solution of sparse linear systems over finite fields. We are able to find the solution of a 100,000 by 100,000 linear system with about 10.3 million non-zero entries over the Galois field with 2 elements using 3 computers in about 54 hours CPU time.}, number={1-3}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Dı́az A. and Hitz, M. and Kaltofen, E. and Lobo, A. and Valente, T.}, year={1995}, month={Jan}, pages={269–282} }
@inbook{chan_díaz_kaltofen_1994, title={A Distributed Approach to Problem Solving in Maple}, ISBN={9780817637910 9781461202639}, url={http://dx.doi.org/10.1007/978-1-4612-0263-9_2}, DOI={10.1007/978-1-4612-0263-9_2}, abstractNote={A system is described whereby a Maple computation can be distributed across a network of computers running Unix. The distribution is based on the DSC system, which can ship source code and input data to carefully selected computers for execution and which can retrieve the produced output data. Our code is fully portable and requires no changes of the underlying Maple or Unix systems. Speedup over Maple’ s built-in sequential procedure is demonstrated when computing determinants of integer matrices.}, booktitle={Maple V: Mathematics and its Applications}, publisher={Birkhäuser Boston}, author={Chan, K. C. and Díaz, A. and Kaltofen, E.}, year={1994}, pages={13–21} }
@inproceedings{kaltofen_1994, title={Asymptotically fast solution of Toeplitz-like singular linear systems}, ISBN={0897916387}, url={http://dx.doi.org/10.1145/190347.190431}, DOI={10.1145/190347.190431}, abstractNote={The Toeplitz-likeness of a matrix (Kailath et al. 1979) is the generalization of the notion that a matrix is Toeplitz. Block matrices with Toeplitz blocks, such as the Sylvester matrix corresponding to the resultant of two univariate polynomials, are Toeplitz-like, as are products and inverses of Toeplitz-like matrices. The displacement rank of a matrix is a measure for the degree of being Toeplitz-like. For example, an r × s block matrix with Toeplitz blocks has displacement rank r+s whereas a generic N × N matrix has displacement rank N . A matrix of displacement rank α can be implicitly represented by a sum of α matrices, each of which is the product of a lower triangular and an upper triangular Toeplitz matrices. Such a ΣLU representation can usually be obtained efficiently. We consider the problem of computing a solution to a possibly singular linear system Ax = b with coefficients in an arbitrary field, where A is an N ×N matrix of displacement rank α given in ΣLU representation. By use of randomization we show that if the system is solvable we can find a vector that is uniformly sampled from the solution manifold in O(αN(log N) loglog N) expected arithmetic operations in the field of entries. In case no solution exists, this fact is discovered by our algorithm. In asymptotically the same time we can also compute the rank of A and the determinant of a non-singular A. Toeplitz and Toeplitz-like matrices and the corresponding linear systems are ubiquitous in control theory, of course, but also in symbolic computation. Examples}, booktitle={Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94}, publisher={ACM Press}, author={Kaltofen, Erich}, year={1994} }
@inproceedings{kaltofen_lobo_1994, title={Factoring high-degree polynomials by the black box Berlekamp algorithm}, ISBN={0897916387}, url={http://dx.doi.org/10.1145/190347.190371}, DOI={10.1145/190347.190371}, abstractNote={Abstract}, booktitle={Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94}, publisher={ACM Press}, author={Kaltofen, Erich and Lobo, Austin}, year={1994} }
@inproceedings{kaltofen_pan_1994, place={Singapore}, title={Parallel solution of Toeplitz and Toeplitz-like linear systems over fields of small positive characteristic}, booktitle={Proceedings of the First International Symposium of Parallel Symbolic Computation}, publisher={World Scientific Publishing Co}, author={Kaltofen, E. and Pan, V.}, editor={Hong, H.Editor}, year={1994}, pages={225–233} }
@inbook{kaltofen_1993, title={Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems}, ISBN={9783540566861 9783540476306}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-56686-4_44}, DOI={10.1007/3-540-56686-4_44}, booktitle={Applied Algebra, Algebraic Algorithms and Error-Correcting Codes}, publisher={Springer Berlin Heidelberg}, author={Kaltofen, Erich}, year={1993}, pages={195–212} }
@book{kaltofen_1993, place={Argonne, Illinois}, title={Computational differentiation and algebraic complexity theory}, number={MCS-TM-183ANL/MCS-TM-183}, journal={Workshop Report on First Theory Institute on Computational Differentiation}, institution={Argonne National Laboratory}, author={Kaltofen, E.}, editor={Bischof, C.H. and Griewank, A. and Khademi, P.M.Editors}, year={1993}, month={Dec}, pages={28–30} }
@article{kaltofen_1993, title={Direct proof of a theorem by Kalkbrener, Sweedler, and Taylor}, volume={27}, ISSN={0163-5824}, url={http://dx.doi.org/10.1145/182125.182126}, DOI={10.1145/182125.182126}, abstractNote={
For given
f
1
,...,
f
m
∈
K
[
x
] that are relatively prime, where
K
is a field, Kalkbrener, Sweedler, and Taylor (1993) present degree bounds on the
a
i
needed to express 1 (and other low degree polynomials) as Σ
a
i
f
i
. Their bounds are an improvement on bounds given by Kakié (1976). This note presents a direct proof of the following fact.
}, number={4}, journal={ACM SIGSAM Bulletin}, publisher={Association for Computing Machinery (ACM)}, author={Kaltofen, Erich}, year={1993}, month={Dec}, pages={2} }
@inbook{kaltofen_1993, place={San Mateo, California}, title={Dynamic parallel evaluation of computation DAGs}, booktitle={Synthesis of Parallel Algorithms}, publisher={Morgan Kaufmann Publishers}, author={Kaltofen, E.}, editor={Reif, J.Editor}, year={1993}, pages={723–758} }
@inproceedings{diaz_hitz_kaltofen_lobo_valente_1993, place={Berlin, Heidelberg}, series={Lecture Notes in Computer Science}, title={Process scheduling in DSC and the large sparse linear systems challenge}, ISBN={354057235X}, url={http://dx.doi.org/10.1007/bfb0013169}, DOI={10.1007/bfb0013169}, booktitle={Design and Implementation of Symbolic Computation Systems (DISCO 1993)}, publisher={Springer-Verlag}, author={Diaz, A. and Hitz, M. and Kaltofen, E. and Lobo, A. and Valente, T.}, year={1993}, pages={66–80}, collection={Lecture Notes in Computer Science} }
@book{kaltofen_1992, place={Troy, New York}, title={Efficient solution of sparse linear systems}, institution={Rensselaer Polytechnic Institute, Department of Computer Science}, author={Kaltofen, E.}, year={1992} }
@inproceedings{kaltofen_1992, title={On computing determinants of matrices without divisions}, ISBN={0897914899}, url={http://dx.doi.org/10.1145/143242.143350}, DOI={10.1145/143242.143350}, abstractNote={An algorithm ~ given that computes the determinant of an n x n matrix with entries fr~rn an arbitrary commutative ring in 0(n3~ ring additions, subtractions, and multiplications; the ‘soft-O” O indicates some missing log n factors. The exponent in the running time can be reduced further by use of asymptotically fast matrix multiplication. The same results hold for computing all nz entries of the adjoint matrix of an n x n matrix with entries from a commutative ring.}, booktitle={Papers from the international symposium on Symbolic and algebraic computation - ISSAC '92}, publisher={ACM Press}, author={Kaltofen, Erich}, year={1992} }
@inbook{kaltofen_1992, place={Berlin, Heidelberg}, series={Lecture Notes in Computer Science}, title={Polynomial factorization 1987–1991}, ISBN={3540552847}, url={http://dx.doi.org/10.1007/bfb0023837}, DOI={10.1007/bfb0023837}, booktitle={LATIN '92}, publisher={Springer-Verlag}, author={Kaltofen, Erich}, year={1992}, pages={294–313}, collection={Lecture Notes in Computer Science} }
@inproceedings{kaltofen_pan_1992, title={Processor-efficient parallel solution of linear systems. II. The positive characteristic and singular cases}, ISBN={0818629002}, url={http://dx.doi.org/10.1109/sfcs.1992.267779}, DOI={10.1109/sfcs.1992.267779}, abstractNote={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.<>}, booktitle={Proceedings., 33rd Annual Symposium on Foundations of Computer Science}, publisher={IEEE}, author={Kaltofen, E. and Pan, V.}, year={1992} }
@inproceedings{diaz_kaltofen_schmitz_valente_1991, place={New York}, title={DSC: a system for distributed symbolic computation}, ISBN={0897914376 9780897914376}, url={http://dx.doi.org/10.1145/120694.120772}, DOI={10.1145/120694.120772}, abstractNote={DSC is a general purpose tool that allows the distribution of a computation over a network of Unix workstations. Its control mechanisms automatically start up daemon processes on the participating workstations in order to communicate data by the standard IP/TCP/UDP protocols. The user's program distributes either remote procedure calls or source code of programs and their corresponding input data files by calling a DSC library function. DSC then automatically finds a suitable workstation and sends the information necessary to execute the given subtask. If source code, which may be written in either ANSI C or Common Lisp, is distributed, this includes compilation on the remote workstation to first make an executable object module. In this mode, a Unix workstation of any architecture type or without prior preparation of problem specific object modules on its file system can be involved. A call to another library function synchronizes the user's program execution by selectively waiting for the completion of a specific or all distributed subtasks. DSC also has an interactive monitor facility that lets a user watch the progress of a distributed computation. We have tested DSC with a primality test for large integers and with a factorization algorithm for polynomials over large finite fields and observed significant speed-ups over executing the best-known methods on a single workstation computation. These experiments have been carried out not only on our local area network but also on off-site workstations at the University of Delaware.}, booktitle={Proceedings of the 1991 international symposium on Symbolic and algebraic computation - ISSAC '91}, publisher={ACM Press}, author={Diaz, A. and Kaltofen, E. and Schmitz, K. and Valente, T.}, editor={Watt, S.M.Editor}, year={1991}, pages={323–332} }
@inproceedings{kaltofen_1991, title={Effective Noether irreducibility forms and applications}, ISBN={0897913973}, url={http://dx.doi.org/10.1145/103418.103431}, DOI={10.1145/103418.103431}, abstractNote={Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree. A (multivariate) polynomial over a specific field is said to be absolutely irreducible if it is irreducible over the algebraic closure of its coefficient field. A specific polynomial of a certain degree is absolutely irreducible, if and only if all the corresponding irreducibility forms vanish when evaluated at the coefficients of the specific polynomial. Our forms have much smaller degrees and coefficients than the forms derived originally by Emmy Noether. We can also apply our estimates to derive more effective versions of irreducibility theorems by Ostrowski and Deuring and of the Hilbert irreducibility theorem. We also give an effective estimate on the diameter of the neighborhood of an absolutely irreducible polynomial with respect to the coefficient space in which absolute irreducibility is preserved. Furthermore, we can apply the effective estimates to derive several factorization results in parallel computational complexity theory: we show how to compute arbitrary high precision approximations of the complex factors of a multivariate integral polynomial and how to count the number of absolutely irreducible factors of a multivariate polynomial with coefficients in a rational function field, both in the complexity class NC. The factorization results also extend to the case where the coefficient field is a function field.}, booktitle={Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91}, publisher={ACM Press}, author={Kaltofen, Erich}, year={1991} }
@inbook{kaltofen_yui_1991, place={New York}, title={Explicit Construction of the Hilbert Class Fields of Imaginary Quadratic Fields by Integer Lattice Reduction}, ISBN={9780387976709 9781475741582}, url={http://dx.doi.org/10.1007/978-1-4757-4158-2_8}, DOI={10.1007/978-1-4757-4158-2_8}, booktitle={Number Theory}, publisher={Springer}, author={Kaltofen, Erich and Yui, Noriko}, editor={Chudnovsky, D.V. and Chudnovsky, G.V. and Cohn, H. and Nathanson, M.B.Editors}, year={1991}, pages={149–202} }
@article{cantor_kaltofen_1991, title={On fast multiplication of polynomials over arbitrary algebras}, volume={28}, ISSN={0001-5903 1432-0525}, url={http://dx.doi.org/10.1007/bf01178683}, DOI={10.1007/bf01178683}, number={7}, journal={Acta Informatica}, publisher={Springer Science and Business Media LLC}, author={Cantor, David G. and Kaltofen, Erich}, year={1991}, month={Jul}, pages={693–701} }
@inbook{kaltofen_saunders_1991, place={Berlin Heidelberg}, series={Lecture Notes in Computer Science}, title={On wiedemann's method of solving sparse linear systems}, ISBN={9783540545224 9783540384366}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-54522-0_93}, DOI={10.1007/3-540-54522-0_93}, booktitle={Applied Algebra, Algebraic Algorithms and Error-Correcting Codes}, publisher={Springer}, author={Kaltofen, Erich and Saunders, B. David}, editor={Mattson, H.F. and Mora, T. and Rao, T.R.N.Editors}, year={1991}, pages={29–38}, collection={Lecture Notes in Computer Science} }
@inproceedings{kaltofen_pan_1991, title={Processor efficient parallel solution of linear systems over an abstract field}, ISBN={0897914384}, url={http://dx.doi.org/10.1145/113379.113396}, DOI={10.1145/113379.113396}, abstractNote={Parallel randomized algorithms are presented that solve n-dimensional systems of linear equations and compute inverses of n × n non-singular matrices over a field in O((log n)) time, where each time unit represents an arithmetic operation in the field generated by the matrix entries. The algorithms utilize within a O(log n) factor as many processors as are needed to multiply two n × n matrices. The algorithms avoid zero divisions with controllably high probability provided the O(n) random elements used are selected uniformly from a sufficiently large set. For fields of small positive characteristic, the processor count measures of our solutions are somewhat higher.}, booktitle={Proceedings of the third annual ACM symposium on Parallel algorithms and architectures - SPAA '91}, publisher={ACM Press}, author={Kaltofen, Erich and Pan, Victor}, year={1991} }
@inproceedings{kaltofen_singer_1991, place={Singapore}, title={Size efficient parallel algebraic circuits for partial derivatives}, booktitle={IV International Conference on Computer Algebra in Physical Research}, publisher={World Scientific Publishing Co.}, author={Kaltofen, E. and Singer, M.F.}, editor={Shirkov, D.V. and Rostovtsev, V.A. and Gerdt, V.P.Editors}, year={1991}, pages={133–145} }
@article{kaltofen_1990, place={London}, title={Algebraic Computational Complexity}, volume={9}, number={3}, journal={Journal of Symbolic Computation}, publisher={Academic Press}, year={1990} }
@inproceedings{rebne_kaltofen_1990, place={Edinburgh, United Kingdom}, title={Computer mathematics systems and a trilateral approach to human resource development in technical occupations}, volume={1}, booktitle={Proceedings of the 7th International Conference on Technology and Education}, publisher={CEP Consultants Ltd}, author={Rebne, D. and Kaltofen, E.}, editor={Estes, N. and Heene, J. and Leclercq, D.Editors}, year={1990}, pages={251–253} }
@article{kaltofen_1990, title={Computing the irreducible real factors and components of an algebraic curve}, volume={1}, ISSN={0938-1279 1432-0622}, url={http://dx.doi.org/10.1007/bf01810297}, DOI={10.1007/bf01810297}, number={2}, journal={Applicable Algebra in Engineering, Communication and Computing}, publisher={Springer Science and Business Media LLC}, author={Kaltofen, Erich}, year={1990}, month={Sep}, pages={135–148} }
@article{kaltofen_trager_1990, title={Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators}, volume={9}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/s0747-7171(08)80015-6}, DOI={10.1016/s0747-7171(08)80015-6}, abstractNote={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. We show that within this 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 all be solved in random polynomial-time. Since we can convert black boxes efficiently to sparse format, problems with sparse solutions, e.g., sparse polynomial factorization and sparse multivariate rational function interpolation, are also in random polynomial time. Moreover, the black box representation is one of the most space efficient implicit representations that we know. Therefore, the output programs can be easily distributed over a network of processors for further manipulation, such as sparse interpolation.}, number={3}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Kaltofen, Erich and Trager, Barry M.}, year={1990}, month={Mar}, pages={301–320} }
@inproceedings{kaltofen_lakshman_wiley_1990, title={Modular rational sparse multivariate polynomial interpolation}, ISBN={0201548925}, url={http://dx.doi.org/10.1145/96877.96912}, DOI={10.1145/96877.96912}, abstractNote={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.
Then the newly developed modular algorithm is presented. The computing times for the speeded Ben-Or and Tiwari and the modular algorithm are compared, and it is shown that the modular algorithm is markedly superior.}, booktitle={Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '90}, publisher={ACM Press}, author={Kaltofen, E. and Lakshman, Y. N. and Wiley, J.-M.}, year={1990} }
@article{kaltofen_krishnamoorthy_saunders_1990, title={Parallel algorithms for matrix normal forms}, volume={136}, ISSN={0024-3795}, url={http://dx.doi.org/10.1016/0024-3795(90)90028-b}, DOI={10.1016/0024-3795(90)90028-b}, abstractNote={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 has two important advantages over our previous one: the multipliers relating the Smith form to the input matrix are computed, and the algorithm is probabilistic of Las Vegas type, i.e., always finds the correct answer. The Smith form algorithm is also a good sequential algorithm. Our algorithm reduces the problem of Smith form computation to two Hermite form computations. Thus the Smith form problem has complexity asymptotically that of the Hermite form problem. We also construct fast parallel algorithms for Jordan normal form and testing similarity of matrices. Both the similarity and non-similarity problems are in the complexity class RNC for the usual coefficient fields, i.e., they can be probabilistically decided in polylogarithmic time using polynomially many processors.}, journal={Linear Algebra and its Applications}, publisher={Elsevier BV}, author={Kaltofen, Erich and Krishnamoorthy, M.S. and Saunders, B. David}, year={1990}, month={Jul}, pages={189–208} }
@inbook{kaltofen_1990, place={New York, NY}, title={Polynomial factorization 1982-1986}, volume={125}, booktitle={Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics}, publisher={Marcel Dekker, Inc}, author={Kaltofen, E.}, editor={Chudnovsky, D.V. and Jenks, R.D.Editors}, year={1990}, pages={285–309} }
@inproceedings{kaltofen_valente_yui_1989, title={An improved Las Vegas primality test}, ISBN={0897913256}, url={http://dx.doi.org/10.1145/74540.74545}, DOI={10.1145/74540.74545}, abstractNote={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(√—D). 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(√—D). The modification we propose determines instead a root of the Watson class equation for Q(√—D) 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.}, booktitle={Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89}, publisher={ACM Press}, author={Kaltofen, E. and Valente, T. and Yui, N.}, year={1989} }
@book{kaltofen_watt_1989, place={New York}, title={Computers and Mathematics}, ISBN={9780387970196 9781461396475}, url={http://dx.doi.org/10.1007/978-1-4613-9647-5}, DOI={10.1007/978-1-4613-9647-5}, publisher={Springer US}, year={1989} }
@article{kaltofen_rolletschek_1989, title={Computing greatest common divisors and factorizations in quadratic number fields}, volume={53}, ISSN={0025-5718}, url={http://dx.doi.org/10.1090/s0025-5718-1989-0982367-2}, DOI={10.1090/s0025-5718-1989-0982367-2}, abstractNote={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 are known. It was shown by Cohn that for D≤−19 even remainder sequences with possibly nondecreasing norms cannot determine the GCD of arbitrary inputs. We extend this result by showing that there does not even exist an input in these domains for which the GCD computation becomes possible by allowing nondecreasing norms or remainders whose norms are not as small as possible. We then provide two algorithms for computing the GCD of algebraic integers in quadratic number fields Q(√D)}, number={188}, journal={Mathematics of Computation}, publisher={American Mathematical Society (AMS)}, author={Kaltofen, Erich and Rolletschek, Heinrich}, year={1989}, pages={697–697} }
@inproceedings{kaltofen_1989, place={New York}, title={Computing the irreducible real factors and components of an algebraicf curve}, ISBN={0897913183 9780897913188}, url={http://dx.doi.org/10.1145/73833.73842}, DOI={10.1145/73833.73842}, abstractNote={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.}, booktitle={Proceedings of the fifth annual symposium on Computational geometry - SCG '89}, publisher={ACM Press}, author={Kaltofen, E.}, editor={Mehlhorn, K.Editor}, year={1989}, month={Jun}, pages={79–87} }
@inbook{kaltofen_1989, place={Greenwhich, Connecticut}, title={Factorization of polynomials given by straight-line programs}, volume={5}, booktitle={Randomness and Computation, Advances in Computing Research}, publisher={JAI Press Inc.}, author={Kaltofen, E.}, editor={Micali, S.Editor}, year={1989}, pages={375–412} }
@inbook{kaltofen_yagati_1989, place={Berlin Heidelberg}, title={Improved sparse multivariate polynomial interpolation algorithms}, ISBN={9783540510840 9783540461531}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-51084-2_44}, DOI={10.1007/3-540-51084-2_44}, abstractNote={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 to Zippel (1988). We present efficient algorithms for finding the rank of certain special Toeplitz systems arising in the Ben-Or and Tiwari algorithm and for solving transposed Vandermonde systems of equations, the use of which greatly improves the time complexities of the two interpolation algorithms.}, booktitle={Symbolic and Algebraic Computation}, publisher={Springer}, author={Kaltofen, Erich and Yagati, Lakshman}, year={1989}, pages={467–474} }
@inbook{kaltofen_krishnamoorthy_saunders_1989, title={Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal form of polynomial matrices}, ISBN={9783540515173 9783540482079}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-51517-8_134}, DOI={10.1007/3-540-51517-8_134}, abstractNote={We have provided a parallel solution for the well-known Smith normal form problem. Our method employs randomization as a tool to remove the iterations along the main diagonal in the classical sequential algorithms, and as such might be useful in similar settings, as well as may speed the sequential methods themselves.}, booktitle={Lecture Notes in Computer Science}, publisher={Springer Berlin Heidelberg}, author={Kaltofen, Erich and Krishnamoorthy, M. S. and Saunders, B. David}, year={1989}, pages={317–322} }
@inproceedings{kaltofen_1989, place={Troy, New York}, title={Parallel algebraic algorithm design}, publisher={Rensselaer Polytechnic Institute, Department of Computer Science}, author={Kaltofen, E.}, year={1989}, month={Jul} }
@inproceedings{canny_kaltofen_yagati_1989, title={Solving systems of nonlinear polynomial equations faster}, ISBN={0897913256}, url={http://dx.doi.org/10.1145/74540.74556}, DOI={10.1145/74540.74556}, abstractNote={Finding the solution to a system of n non-linear polynomial equations in n unknowns over a given field, say the algebraic closure of the coefficient field, is a classical and fundamental problem in computational algebra. For algebraic reasons (refer to footnote 1 in van der Waerden (1953, §80)) one considers projective problems, that is, the polynomials are homogeneous and the solutions are sought in n-dimensional projective space. Note also that the solutions of an affine system are specializations of the solution rays of its homogenized projective version. Going back to Cayley and Bezout in the last century, solvability of such a projective system is determined by the vanishing of a certain invariant, its resultant. This invariant generalizes the Sylvester resultant of two polynomials in a single variable (Knuth 1981) and the determinant of the coefficient matrix on a homogeneous linear system. In 1916 Macaulay (1916) showed that the resultant can be expressed by a quotient of two determinants whose correspond-}, booktitle={Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89}, publisher={ACM Press}, author={Canny, J. F. and Kaltofen, E. and Yagati, L.}, year={1989} }
@article{gregory_kaltofen_1988, title={Analysis of the binary complexity of asymptotically fast algorithms for linear system solving}, volume={22}, ISSN={0163-5824}, url={http://dx.doi.org/10.1145/43876.43880}, DOI={10.1145/43876.43880}, abstractNote={Two significant developments can be distinguished in the theory of algebraic algorithm design. One is that of fast algorithms in terms of counting the arithmetic operations, such as the asymptotically fast matrix multiplication procedures and related linear algebra algorithms or the asymptotically fast polynomial multiplication procedures and related polynomial manipulation algorithms. The other is to observe the actual bit complexity when such algorithms are performed for concrete fields, in particular the rational numbers. It was discovered in the mid-1960s that for rational polynomial GCD operations the classical algorithm can lead to exponential coefficient size growth. The beautiful theory of subresultants by Collins [7] and Brown & Traub [5] explains, however, that the size growth is not inherent but a consequence of over-simplified rational arithmetic. Similar phenomena were observed for the Gaussian elimination procedure [2], [9].}, number={2}, journal={ACM SIGSAM Bulletin}, publisher={Association for Computing Machinery (ACM)}, author={Gregory, Brent and Kaltofen, Erich}, year={1988}, month={Apr}, pages={41–49} }
@inproceedings{kaltofen_trager_1988, title={Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators}, ISBN={0818608773}, url={http://dx.doi.org/10.1109/sfcs.1988.21946}, DOI={10.1109/sfcs.1988.21946}, abstractNote={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.<>}, booktitle={[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science}, publisher={IEEE}, author={Kaltofen, E. and Trager, B.}, year={1988} }
@article{freeman_imirzian_kaltofen_yagati_1988, title={Dagwood: a system for manipulating polynomials given by straight-line programs}, volume={14}, ISSN={0098-3500}, url={http://dx.doi.org/10.1145/44128.214376}, DOI={10.1145/44128.214376}, abstractNote={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.}, number={3}, journal={ACM Transactions on Mathematical Software}, publisher={Association for Computing Machinery (ACM)}, author={Freeman, Timothy S. and Imirzian, Gregory M. and Kaltofen, Erich and Yagati, Lakshman}, year={1988}, month={Sep}, pages={218–240} }
@article{miller_ramachandran_kaltofen_1988, title={Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits}, volume={17}, ISSN={0097-5397 1095-7111}, url={http://dx.doi.org/10.1137/0217044}, DOI={10.1137/0217044}, abstractNote={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×n matrices over the semi-ring R in O (log n) time.}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Miller, Gary L. and Ramachandran, Vijaya and Kaltofen, Erich}, year={1988}, month={Aug}, pages={687–695} }
@article{kaltofen_1988, title={Greatest common divisors of polynomials given by straight-line programs}, volume={35}, ISSN={0004-5411}, url={http://dx.doi.org/10.1145/42267.45069}, DOI={10.1145/42267.45069}, abstractNote={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.}, number={1}, journal={Journal of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Kaltofen, Erich}, year={1988}, month={Jan}, pages={231–264} }
@article{kaltofen_1987, title={Computer Algebra Algorithms}, volume={2}, ISSN={8756-7016 8756-7016}, url={http://dx.doi.org/10.1146/annurev.cs.02.060187.000515}, DOI={10.1146/annurev.cs.02.060187.000515}, abstractNote={INTRODUCTION ...................................................................................................................... 1 ARITHMETIC ........................................................................................................................... 2 Integer and Polynomial Addition, Multiplication, and Division with Remainder ............. 2 Integer and Polynomial Greatest Common Divisor ........................................................... 3 Floating Point Number s and Power Series........................................................................ 5 Matrix Arithmetic............................................................................................................... 6 Arithmetic with Concisely Represented Expr essions ......................................................... 7 SEMINAL PROBLEMS ............................................................................................................. 9 Factorization ...................................................................................................................... 9 Computing with Gr oups ..................................................................................................... 11 Integration in Closed F orm ................................................................................................ 12 Solving Systems of Polynomial Equations ......................................................................... 14 Decision Methods for Elementary Algebr a and Geometry................................................ 16 LINKAGES ................................................................................................................................ 17 Parallel Algorithms............................................................................................................ 17 Logic Programming and Simplification............................................................................. 18 Language and System Design ............................................................................................ 18 Activities Outside Computer Algebr a ................................................................................ 19 CONCLUSION .......................................................................................................................... 19 LITERATURE CITED............................................................................................................... 21}, number={1}, journal={Annual Review of Computer Science}, publisher={Annual Reviews}, author={Kaltofen, E}, year={1987}, month={Jun}, pages={91–118} }
@article{kaltofen_1987, title={Deterministic irreducibility testing of polynomials over large finite fields}, volume={4}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/s0747-7171(87)80055-x}, DOI={10.1016/s0747-7171(87)80055-x}, abstractNote={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 probabilistic nature. Our deterministic solution is based on our algorithm for absolute irreducibility testing combined with Berlekamp's algorithm.}, number={1}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Kaltofen, Erich}, year={1987}, month={Aug}, pages={77–82} }
@article{kaltofen_krishnamoorthy_saunders_1987, title={Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices}, volume={8}, ISSN={0196-5212 2168-345X}, url={http://dx.doi.org/10.1137/0608057}, DOI={10.1137/0608057}, abstractNote={Boolean circuits of polynomial size and polylogarithmic depth are given for computing the Hermite and Smith normal forms of polynomial matrices over finite fields and the field of rational numbers. The circuits for the Smith normal form computation are probabilistic ones and also determine very efficient sequential algorithms. Furthermore, we give a polynomial-time deterministic sequential algorithm for the Smith normal form over the rationals. The Smith normal form algorithms are applied to the rational canonical form of matrices over finite fields and the field of rational numbers.}, number={4}, journal={SIAM Journal on Algebraic Discrete Methods}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Kaltofen, Erich and Krishnamoorthy, M. S. and Saunders, B. David}, year={1987}, month={Oct}, pages={683–690} }
@book{cantor_kaltofen_1987, place={Troy, NY}, title={Fast multiplication of polynomials over arbitrary rings}, number={87-35}, institution={Rensselaer Polytechnic Institute, Department of Computer Science}, author={Cantor, David G. and Kaltofen, Erich}, year={1987}, month={Dec} }
@inproceedings{kaltofen_1987, title={Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials}, ISBN={0897912217}, url={http://dx.doi.org/10.1145/28395.28443}, DOI={10.1145/28395.28443}, abstractNote={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.}, booktitle={Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87}, publisher={ACM Press}, author={Kaltofen, E.}, year={1987} }
@inproceedings{freeman_imirzian_kaltofen_1986, title={A system for manipulating polynomials given by straight-line programs}, ISBN={0897911997}, url={http://dx.doi.org/10.1145/32439.32473}, DOI={10.1145/32439.32473}, abstractNote={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, 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.}, booktitle={Proceedings of the fifth ACM symposium on Symbolic and algebraic computation - SYMSAC '86}, publisher={ACM Press}, author={Freeman, T. and Imirzian, G. and Kaltofen, E.}, year={1986} }
@inbook{miller_ramachandran_kaltofen_1986, title={Efficient parallel evaluation of straight-line code and arithmetic circuits}, ISBN={9783540167662 9783540387466}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-16766-8_21}, DOI={10.1007/3-540-16766-8_21}, booktitle={VLSI Algorithms and Architectures}, publisher={Springer Berlin Heidelberg}, author={Miller, Gary L and Ramachandran, Vijaya and Kaltofen, Erich}, year={1986}, pages={236–245} }
@inproceedings{kaltofen_krishnamoorthy_saunders_1986, title={Fast parallel algorithms for similarity of matrices}, ISBN={0897911997}, url={http://dx.doi.org/10.1145/32439.32452}, DOI={10.1145/32439.32452}, abstractNote={Article Fast parallel algorithms for similarity of matrices Share on Authors: E. Kaltofen Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile , M. Krishnamoorthy Univ. of Delaware, Newark Univ. of Delaware, NewarkView Profile , B. D. Saunders Math. Sci. Research Inst., Berkeley, CA Math. Sci. Research Inst., Berkeley, CAView Profile Authors Info & Claims SYMSAC '86: Proceedings of the fifth ACM symposium on Symbolic and algebraic computationOctober 1986 Pages 65–70https://doi.org/10.1145/32439.32452Published:01 October 1986 6citation196DownloadsMetricsTotal Citations6Total Downloads196Last 12 Months0Last 6 weeks0 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}, booktitle={Proceedings of the fifth ACM symposium on Symbolic and algebraic computation - SYMSAC '86}, publisher={ACM Press}, author={Kaltofen, E. and Krishnamoorthy, M. and Saunders, B. D.}, year={1986} }
@inproceedings{kaltofen_1986, title={Uniform closure properties of P-computable functions}, ISBN={0897911938}, url={http://dx.doi.org/10.1145/12130.12163}, DOI={10.1145/12130.12163}, abstractNote={Val iant [1] introduced the notion of a family of 19computable polynomials as those mul t ivar ia te polynomials of polynomial ly-bounded degree and straight-l ine computat ion length. He raised the question of whether pcomputable families would be closed under natural mathemat ica l operations and showed tha t this is true for taking repeated part ial derivatives in a single variable, whereas by taking repeated part ial derivatives in many variables one can obtain the general permanent from a polynomial-sized formula.}, booktitle={Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86}, publisher={ACM Press}, author={Kaltofen, E}, year={1986} }
@inproceedings{kaltofen_1985, title={Computing with polynomials given by straight-line programs I: greatest common divisors}, ISBN={0897911512}, url={http://dx.doi.org/10.1145/22145.22160}, DOI={10.1145/22145.22160}, abstractNote={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.}, booktitle={Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85}, publisher={ACM Press}, author={Kaltofen, E}, year={1985} }
@inproceedings{kaltofen_1985, title={Computing with polynomials given by straight-line programs II sparse factorization}, ISBN={0818606444}, url={http://dx.doi.org/10.1109/sfcs.1985.17}, DOI={10.1109/sfcs.1985.17}, abstractNote={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.}, booktitle={26th Annual Symposium on Foundations of Computer Science (sfcs 1985)}, publisher={IEEE}, author={Kaltofen, Erich}, year={1985} }
@article{kaltofen_1985, title={Effective Hilbert irreducibility}, volume={66}, ISSN={0019-9958}, url={http://dx.doi.org/10.1016/s0019-9958(85)80056-5}, DOI={10.1016/s0019-9958(85)80056-5}, abstractNote={In this paper we prove by entirely elementary means a very effective version of the Hilbert irreducibility theorem. We then apply our theorem to construct a probabilistic irreducibility test for sparse multivariate polynomials over arbitrary perfect fields. For the usual coefficient fields the test runs in polynomial time in the input size.}, number={3}, journal={Information and Control}, publisher={Elsevier BV}, author={Kaltofen, Erich}, year={1985}, month={Sep}, pages={123–137} }
@article{von zur gathen_kaltofen_1985, title={Factoring sparse multivariate polynomials}, volume={31}, ISSN={0022-0000}, url={http://dx.doi.org/10.1016/0022-0000(85)90044-3}, DOI={10.1016/0022-0000(85)90044-3}, abstractNote={This paper presents a probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the size of sparse representations of input plus output, provided the number of irreducible factors is bounded. We thus obtain probabilistic polynomial-time factoring procedures over algebraic number fields and over finite fields. The reduction is based on an effective version of Hilbert's irreducibility theorem.}, number={2}, journal={Journal of Computer and System Sciences}, publisher={Elsevier BV}, author={von zur Gathen, Joachim and Kaltofen, Erich}, year={1985}, month={Oct}, pages={265–287} }
@article{von zur gathen_kaltofen_1985, title={Factorization of multivariate polynomials over finite fields}, volume={45}, ISSN={0025-5718}, url={http://dx.doi.org/10.1090/s0025-5718-1985-0790658-x}, DOI={10.1090/s0025-5718-1985-0790658-x}, abstractNote={We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field.}, number={171}, journal={Mathematics of Computation}, publisher={American Mathematical Society (AMS)}, author={von zur Gathen, J. and Kaltofen, E.}, year={1985}, month={Sep}, pages={251–251} }
@article{kaltofen_1985, title={Fast parallel absolute irreducibility testing}, volume={1}, ISSN={0747-7171}, url={http://dx.doi.org/10.1016/s0747-7171(85)80029-8}, DOI={10.1016/s0747-7171(85)80029-8}, abstractNote={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 establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coeffieients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial's irreducibility in the algebraic closure of the finite field of order p is not preserved.}, number={1}, journal={Journal of Symbolic Computation}, publisher={Elsevier BV}, author={Kaltofen, Erich}, year={1985}, month={Mar}, pages={57–67} }
@article{kaltofen_1985, title={Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization}, volume={14}, ISSN={0097-5397 1095-7111}, url={http://dx.doi.org/10.1137/0214035}, DOI={10.1137/0214035}, abstractNote={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. Lovasz’ 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, w...}, number={2}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Kaltofen, Erich}, year={1985}, month={May}, pages={469–489} }
@inbook{kaltofen_1985, title={Sparse hensel lifting}, ISBN={9783540159841 9783540396857}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-15984-3_230}, DOI={10.1007/3-540-15984-3_230}, abstractNote={A new 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 scheme and only requires the factorization of a single univariate image. The algorithm also provides the content of the input polynomial in the main variable as a by-product. We show how we can take advantage of this property when computing the GCD of multivariate polynomials by sparse Hensel lifting.}, booktitle={EUROCAL '85}, publisher={Springer Berlin Heidelberg}, author={Kaltofen, Erich}, year={1985}, pages={4–17} }
@book{kaltofen_pan_1985, title={The integer manipulation techniques can compete with the linear algebra methods for solving sparse linear systems}, number={85-6}, institution={State University of New York at Albany, Computer Science Department}, author={Kaltofen, E. and Pan, V.}, year={1985} }
@inbook{kaltofen_1984, place={Berlin, Heidelberg}, series={Lecture Notes in Computer Science}, title={A note on the Risch differential equation}, ISBN={354013350X}, url={http://dx.doi.org/10.1007/bfb0032858}, DOI={10.1007/bfb0032858}, booktitle={EUROSAM 84}, publisher={Springer-Verlag}, author={Kaltofen, Erich}, editor={Fitch, J.Editor}, year={1984}, month={Dec}, pages={359–366}, collection={Lecture Notes in Computer Science} }
@inbook{kaltofen_1984, title={Effective Hilbert irreducibility}, ISBN={354013350X}, url={http://dx.doi.org/10.1007/bfb0032850}, DOI={10.1007/bfb0032850}, booktitle={EUROSAM 84}, publisher={Springer-Verlag}, author={Kaltofen, Erich}, year={1984}, pages={277–284} }
@inbook{kaltofen_1984, place={Amsterdam}, title={On a theorem by R. Dedekind}, booktitle={DOPO LE PAROLE, Album in Honor of A. K. Lenstra's Doctorate}, author={Kaltofen, E.}, editor={Lenstra, H.W., Jr. and Lenstra, J.K. and van Emde Boas, P.Editors}, year={1984}, month={May} }
@book{kaltofen_1984, place={Troy, New York}, title={The algebraic theory of integration}, institution={Rensselaer Polytechnic Institute, Department of Computer Science}, author={Kaltofen, E.}, year={1984} }
@inproceedings{kaltofen_yui_1984, title={The modular equation of order 11}, booktitle={Third Macsyma Users' Conference}, publisher={General Electric}, author={Kaltofen, E. and Yui, N.}, year={1984}, pages={472–485} }
@article{kaltofen_musser_saunders_1983, title={A Generalized Class of Polynomials that are Hard to Factor}, volume={12}, ISSN={0097-5397 1095-7111}, url={http://dx.doi.org/10.1137/0212031}, DOI={10.1137/0212031}, abstractNote={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.}, number={3}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Kaltofen, Erich and Musser, David R. and Saunders, B. David}, year={1983}, month={Aug}, pages={473–483} }
@inbook{kaltofen_1983, title={On the complexity of finding short vectors in integer lattices}, ISBN={9783540128687 9783540387565}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/3-540-12868-9_107}, DOI={10.1007/3-540-12868-9_107}, abstractNote={In [Lenstra, A., et al. 82] an algorithm is presented which, given n linearly independent n-dimensional integer vectors, calculates a vector in the integer lattice spanned by these vectors whose Euclidean length is within a factor of 2(n−1)/2 of the length of the shortest vector in this lattice. If B denotes the maximum length of the basis vectors, the algorithm is shown to run in O(n 6(log B)3) binary steps. We prove that this algorithm can actually be executed in O(n 6(log B)2+n 5(log B)3) binary steps by analyzing a modified version of the algorithm which also performs better in practice.}, booktitle={Lecture Notes in Computer Science}, publisher={Springer Berlin Heidelberg}, author={Kaltofen, Erich}, year={1983}, pages={236–244} }
@inbook{von zur gathen_kaltofen_1983, place={Berlin Heidelberg}, series={Lecture Notes in Computer Science}, title={Polynomial-time factorization of multivariate polynomials over finite fields}, ISBN={9783540123170 9783540400387}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/bfb0036913}, DOI={10.1007/bfb0036913}, abstractNote={We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e. in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. Also a deterministic version of the algorithm is discussed whose running time is polynomial in the degree of the input polynomial and the size of the field.}, booktitle={Automata, Languages and Programming}, publisher={Springer}, author={von zur Gathen, J. and Kaltofen, E.}, year={1983}, pages={250–263}, collection={Lecture Notes in Computer Science} }
@inproceedings{kaltofen_1982, title={A polynomial reduction from multivariate to bivariate integral polynomial factorization.}, ISBN={0897910702}, url={http://dx.doi.org/10.1145/800070.802200}, DOI={10.1145/800070.802200}, abstractNote={Given an arbitrary but fixed integer r -&-ge; 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.}, booktitle={Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82}, publisher={ACM Press}, author={Kaltofen, Erich}, year={1982} }
@inproceedings{kaltofen_1982, title={A polynomial-time reduction from bivariate to univariate integral polynomial factorization}, url={http://dx.doi.org/10.1109/sfcs.1982.56}, DOI={10.1109/sfcs.1982.56}, abstractNote={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.}, booktitle={23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)}, publisher={IEEE}, author={Kaltofen, Erich}, year={1982}, month={Nov} }
@inbook{kaltofen_1982, place={Vienna}, series={Computing Supplementum}, title={Factorization of Polynomials}, ISBN={9783211816844 9783709134061}, ISSN={0344-8029}, url={http://dx.doi.org/10.1007/978-3-7091-3406-1_8}, DOI={10.1007/978-3-7091-3406-1_8}, abstractNote={Algorithms for factoring polynomials in one or more variables over various coefficient domains are discussed. Special emphasis is given to finite fields, the integers, or algebraic extensions of the rationals, and to multivariate polynomials with integral coefficients. In particular, various squarefree decomposition algorithms and Hensel lifting techniques are analyzed. An attempt is made to establish a complete historic trace for today’s methods. The exponential worst case complexity nature of these algorithms receives attention.}, booktitle={Computing Supplementum}, publisher={Springer}, author={Kaltofen, E.}, editor={Buchberger, B. and Collins, G.E. and Loos, R.Editors}, year={1982}, pages={95–113}, collection={Computing Supplementum} }
@phdthesis{kaltofen_1982, place={Troy, NY}, title={On the complexity of factoring polynomials with integer coefficients}, school={Rensselaer Polytechnic Institute}, author={Kaltofen, E.}, year={1982}, month={Dec} }
@inproceedings{kaltofen_musser_saunders_1981, title={A generalized class of polynomials that are hard to factor}, ISBN={0897910478}, url={http://dx.doi.org/10.1145/800206.806394}, DOI={10.1145/800206.806394}, abstractNote={A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time. The 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.}, booktitle={Proceedings of the fourth ACM symposium on Symbolic and algebraic computation - SYMSAC '81}, publisher={ACM Press}, author={Kaltofen, Erich and Musser, David R. and Saunders, B. David}, year={1981} }
@book{kaltofen_abdali_1981, place={Troy, NY}, title={An attributed LL(1) compilation of Pascal into the lambda-calculus}, number={CS-8103}, institution={Rensselaer Polytechnic Institute Mathematical Sciences Department}, author={Kaltofen, E. and Abdali, S.K.}, year={1981} }
@book{kaltofen_1980, place={Troy, NY}, title={LISP/370 under the Michigan Terminal System}, institution={Rensselaer Polytechnic Institute, Mathematical Sciences Department}, author={Kaltofen, E.}, year={1980}, month={Aug} }