Is this your profile?
Claim your Citation Index profile in order to display more information about you and gain access to Libraries services. Just create or connect your ORCID iD.
Create or connect your ORCID iD
Works (181)
Updated: October 1st, 2024 05:04
2024 article
Encounters in Symbolic Computation: Ideas for the Ages
PROCEEDINGS OF THE 2024 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2024, pp. 1–7.
author keywords: History of polynomial factorization; computation of digits of pi; randomized linear algebra; Freivalds's algorithm; Wiedemann's algorithm
Source: Web Of Science
Added: September 23, 2024
2024 article
Sparse Polynomial Interpolation With Error Correction: Higher Error Capacity by Randomization
PROCEEDINGS OF THE 2024 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2024, pp. 264–273.
author keywords: sparse model fitting; outlier error correction; orthogonal polynomial basis; Prony interpolation algorithm
Source: Web Of Science
Added: September 23, 2024
2022 article
Sparse Polynomial Hermite Interpolation
PROCEEDINGS OF THE 2022 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2022, pp. 469–478.
author keywords: model fitting; gradient data; measurement minimization
TL;DR:
These algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases, and have algorithms that can correct errors in the points by oversampling at a limited number of good values.
(via Semantic Scholar)
Source: Web Of Science
Added: September 11, 2023
2022 article
The GKR Protocol Revisited: Nearly Optimal Prover-Complexity For Polynomial-Time Wiring Algorithms and For Primality Testing in n(1/2+o(1)) Rounds
PROCEEDINGS OF THE 2022 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, ISSAC 2022, pp. 177–186.
author keywords: cloud computing; primality testing; proof-of-work certificate
TL;DR:
This 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.
(via Semantic Scholar)
Source: Web Of Science
Added: September 11, 2023
2020 journal article
A Note on Sparse Polynomial Interpolation in Dickson Polynomial Basis
ACM COMMUNICATIONS IN COMPUTER ALGEBRA, 54(4), 125–128.
TL;DR:
The sparsity t≪ deg(f) with respect to the basis Pn has been exploited 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.
(via Semantic Scholar)
Source: Web Of Science
Added: June 10, 2021
2020 article
Foreword
JOURNAL OF SYMBOLIC COMPUTATION, Vol. 105, pp. 1–3.
Source: Web Of Science
Added: February 15, 2021
2020 journal article
On computing the degree of a Chebyshev Polynomial from its value
JOURNAL OF SYMBOLIC COMPUTATION, 104, 159–167.
author keywords: Algorithms; Discrete logarithms; Chebyshev Polynomials; Interpolation in terms of the Chebyshev; Polynomials of the First Kind
TL;DR:
An algorithm is given that 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 ).
(via Semantic Scholar)
Source: Web Of Science
Added: January 19, 2021
2020 journal article
Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding
IEEE TRANSACTIONS ON INFORMATION THEORY, 67(1), 232–243.
author keywords: Sparse polynomial interpolation; error correction; black box polynomial; list-decoding
TL;DR:
Sparse interpolation algorithms for recovering a polynomial with LaTeX terms from inline-formula evaluations at distinct values for the variable with Chebyshev Basis, which return a list of valid sparse interpolants for the algorithm.
(via Semantic Scholar)
open access via arxiv.org (repository)
Source: Web Of Science
Added: January 19, 2021
2019 journal article
Computing Approximate Greatest Common Right Divisors of Differential Polynomials
Foundations of Computational Mathematics.
author keywords: Symbolic-numeric computation; Approximate polynomial computation; Approximate GCD; Differential polynomials; Linear differential operators
TL;DR:
The approximate greatest common right divisor problem (GCRD) of differential polynomials is introduced, as a non-commutative generalization of the well-studied approximate GCD problem.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2019 article
Elimination-based certificates for triangular equivalence and rank profiles
JOURNAL OF SYMBOLIC COMPUTATION, Vol. 98, pp. 246–269.
author keywords: Interactive certificate; Rank profile; Linear algebra; Triangular equivalence; Verifiable computing
TL;DR:
Novel certificates for triangular equivalence and rank profiles are given, enabling somebody to verify the row or column rank profiles or the whole rank profile matrix faster than recomputing them, with a negligible overall overhead.
(via Semantic Scholar)
Source: Web Of Science
Added: December 30, 2019
2018 article
Sparse Polynomial Interpolation With Arbitrary Orthogonal Polynomial Bases
ISSAC'18: PROCEEDINGS OF THE 2018 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, pp. 223–230.
TL;DR:
These algorithms deterministically recover the sparse representation in the First, Second, Third and Fourth Kind Chebyshev representation from exactly t + B evaluations, and generalize to bases whose ChebysHEv recurrences have parametric scalars.
(via Semantic Scholar)
Source: Web Of Science
Added: February 25, 2019
2017 conference paper
Early Termination in Parametric Linear System Solving and Rational Function Vector Recovery with Error Correction
Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '17. Presented at the the 2017 ACM.
Event: the 2017 ACM
TL;DR:
An algorithm that given the same inputs uses possibly fewer evaluations to compute the solution and may recover it from fewer evaluations than generalized Welch/Berlekamp decoding, and develops a combined early termination algorithm.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
9. Industry, Innovation and Infrastructure
(Web of Science)
Source: Crossref
Added: July 21, 2019
2017 conference paper
Polynomial Time Interactive Proofs for Linear Algebra with Exponential Matrix Dimensions and Scalars Given by Polynomial Time Circuits
Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '17. Presented at the the 2017 ACM.
Event: the 2017 ACM
TL;DR:
An interactive probabilistic proof protocol that certifies in (log N)O(1) arithmetic and Boolean operations for the verifier the determinant 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 is polynomial time uniform.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2016 article
Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
PROCEEDINGS OF THE 2016 ACM INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION (ISSAC 2016), pp. 199–206.
TL;DR:
An algorithm is given 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.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2016 conference paper
Numerical Sparsity Determination and Early Termination
Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '16. Presented at the the ACM.
Event: the ACM
author keywords: Hankel matrix; Vandermonde matrix; sparse polynomial interpolation; condition number; early termination; sparse signal processing
TL;DR:
An algorithm is given that can be used to compute the sparsity and estimate the minimal number of samples needed in numerical sparse interpolation and the early termination strategy of polynomial interpolation has been incorporated in the algorithm.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2015 conference paper
Error-Correcting Sparse Interpolation in the Chebyshev Basis
Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation - ISSAC '15. Presented at the the 2015 ACM.
Event: the 2015 ACM
author keywords: sparse polynomial interpolation; Prony's algorithm; Chebyshev polynomials; Descartes' rule of signs; orthogonal basis; error-correcting code
TL;DR:
The correctness of the list-decoder-based algorithm with a Descartes-rule-of-signs-like property for sparse polynomials in Chebyshev basis is proved and the many techniques for the sparse interpolation in power basis, for instance, supersparse (lacunary) interpolation over large finite fields, are made available to interpolation on Chebyshv basis.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2015 book
PASCO '15 Proceedings of the 2015 International Workshop on Parallel Symbolic Computation
New York, NY: Association for Computing Machinery.
Ed(s): J. Dumas, & C. Pernet
Source: NC State University Libraries
Added: August 16, 2021
2015 journal article
Sparse multivariate function recovery with a small number of evaluations
JOURNAL OF SYMBOLIC COMPUTATION, 75, 209–218.
author keywords: Error correcting coding; Fault tolerance; Cauchy interpolation; Multivariate rational function model
TL;DR:
Here it is proved that T + O ( 1 ) evaluations at random points indeed suffice, thus providing the missing proof to Theorem 2.1 in Section 2 of the ISSAC 2014 paper.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2014 conference paper
Cleaning-up data for sparse model synthesis
Proceedings of the 2014 Symposium on Symbolic-Numeric Computation - SNC '14. Presented at the the 2014 Symposium.
Event: the 2014 Symposium
TL;DR:
The pioneering creation of interpolation algorithms that can account for sparsity in the resulting multi-dimensional models are created, for example, by Zippel, Ben-Or and Tiwari and Kaltofen-Yang-Zhi.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2014 conference paper
Essentially optimal interactive certificates in linear algebra
Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14. Presented at the the 39th International Symposium.
Event: the 39th International Symposium
TL;DR:
All the authors' certificates are based on interactive verification protocols with the interaction removed by a Fiat-Shamir identification heuristic, and the validity of the verification procedure is subject to standard computational hardness assumptions from cryptography.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2014 conference paper
Numerical linear system solving with parametric entries by error correction
Proceedings of the 2014 Symposium on Symbolic-Numeric Computation - SNC '14. Presented at the the 2014 Symposium.
Event: the 2014 Symposium
TL;DR:
The algorithm generalizes Welch/Berlekamp decoding of Reed/Solomon error correcting codes and their numeric floating point counterparts and gives an algorithm that computes the unique solution, which is a vector of rational functions, by evaluating the parameter u at distinct points.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2014 chapter
Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations
In Computer Mathematics (pp. 183–197).
TL;DR:
By way of experiments, the techniques can recover approximate sparse shifted polynomial models, provided that there are few terms \(t\), few outliers and that the sparse shift is relatively small.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2014 conference paper
Sparse multivariate function recovery with a high error rate in the evaluations
Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14. Presented at the the 39th International Symposium.
Event: the 39th International Symposium
TL;DR:
A different algorithm is presented that can interpolate a sparse multivariate rational function from evaluations where the error rate is 1/q for any q > 2, which the ISSAC 2013 algorithm could not handle.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2014 conference paper
Sparse polynomial interpolation codes and their decoding beyond half the minimum distance
Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14. Presented at the the 39th International Symposium.
Event: the 39th International Symposium
TL;DR:
A 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.
(via Semantic Scholar)
Source: Crossref
Added: July 21, 2019
2014 chapter
Symbolic Computation and Complexity Theory Transcript of My Talk
In Computer Mathematics (pp. 3–7).
TL;DR:
I gave talks at the conference Alan Turing’s Heritage: Logic, Computation & Complexity in Lyon, France, and at the Tenth Asian Symposium on Computer Mathematics (ASCM) in Beijing, China, on the complexity theoretic hardness of many problems that the discipline of symbolic computation tackles.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2013 journal article
A fraction free Matrix Berlekamp/Massey algorithm
LINEAR ALGEBRA AND ITS APPLICATIONS, 439(9), 2515–2526.
author keywords: Exact division; Linear recurrences; Matrix recurrences; Block Hankel systems; Block Toeplitz systems; Integer sequences
TL;DR:
This new scalar algorithm has smaller intermediate values than the known fraction free Berlekamp/Massey algorithm and performs all operations in the integral domain, so all divisions performed are exact.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2013 chapter
Factorization of multivariate polynomials
In G. L. Mullen & D. Panario (Eds.), Handbook of Finite Fields (pp. 382–392). Boca Raton, Florida: CRC Press, Taylor & Francis Group.
Ed(s): G. Mullen & D. Panario
Source: NC State University Libraries
Added: March 26, 2022
2013 journal article
On the Matrix Berlekamp-Massey Algorithm
ACM TRANSACTIONS ON ALGORITHMS, 9(4).
author keywords: Linear generated sequences; matrix polynomials; minimal generators; vector Berlekamp/Massey algorithm; multivariable linear control
TL;DR:
This work analyzes the Matrix Berlekamp/Massey algorithm and gives 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.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2013 conference paper
Sparse multivariate function recovery from values with noise and outlier errors
Proceedings of the 38th international symposium on International symposium on symbolic and algebraic computation - ISSAC '13. Presented at the the 38th international symposium.
Event: the 38th international symposium
TL;DR:
This work gives a different univariate solution based on structured linear algebra that yields a stable decoder with floating point arithmetic that can build a sparse model from a number of evaluations that is linear in the sparsity of the model.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2012 conference paper
Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation - ISSAC '12. Presented at the the 37th International Symposium.
Event: the 37th International Symposium
TL;DR:
The algorithm is demonstrated 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.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2012 conference paper
Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation
Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation - SNC '11. Presented at the the 2011 International Workshop.
Event: the 2011 International Workshop
Source: Crossref
Added: July 27, 2019
2012 conference paper
Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values
Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation - ISSAC '12. Presented at the the 37th International Symposium.
Event: the 37th International Symposium
TL;DR:
The Majority Rule Berlekamp/Massey algorithm, which can recover the unique minimal linear generator of degree <i>t</i> when given bounds and the Majority Rule algorithm yields a unique sparse interpolant for the first problem.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2011 journal article
Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
Journal of Symbolic Computation, 47(1), 1–15.
author keywords: Semidefinite programming; Sum-of-squares; Validated output; Hybrid method
TL;DR:
This work presents 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 twoPolynomial sum-of-squares (SOS) with rational coefficient.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
4. Quality Education
(OpenAlex)
11. Sustainable Cities and Communities
(Web of Science)
Source: Crossref
Added: July 27, 2019
2011 journal article
On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field
JOURNAL OF SYMBOLIC COMPUTATION, 47(4), 480–491.
author keywords: Toeplitz matrix; Hankel matrix; Block matrix; Finite field; Singularity counts; Fixed entry; Berlekamp/Massey algorithm
TL;DR:
An explicit count for the number of singular nxn Hankel (Toeplitz) matrices whose entries range over a finite field with q elements is derived by observing the execution of the Berlekamp/Massey algorithm on its elements.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
9. Industry, Innovation and Infrastructure
(Web of Science)
Source: Web Of Science
Added: August 6, 2018
2011 conference paper
Quadratic-time certificates in linear algebra
Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11. Presented at the the 36th international symposium.
Event: the 36th international symposium
Source: Crossref
Added: August 18, 2019
2011 article
Special Issue on Symbolic and Algebraic Computation Foundations, Algorithmics and Applications: ISSAC 2009
Johnson, J. R., Kaltofen, E., & Park, H. (2012, July). JOURNAL OF SYMBOLIC COMPUTATION, Vol. 47, pp. 751–751.
TL;DR:
The papers included in the Special Issue cover investigations on computational homology, fast algorithms for computing order bases of matrices of power series, fast arithmetic in Artin–Schreier towers with applications to elliptic curves, polynomial system solving, and quantifier elimination.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2011 conference paper
Supersparse black box rational function interpolation
Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11. Presented at the the 36th international symposium.
Event: the 36th international symposium
TL;DR:
A method for interpolating a supersparse blackbox rational function with rational coefficients, for example, a ratio of binomials or trinomials with very high degree, which is very effective for rational functions with a small number of non-zero terms, but it quickly becomes ineffective for a high number of terms.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2011 other
Symmetric determinantal representation of formulas and weakly skew circuits
Source: Crossref
Added: July 27, 2019
2011 conference paper
Symmetric determinantal representation of weakly skew circuits
In C. Dürr & T. Schwentick (Eds.), Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2011) (pp. 543–554). Germany.
Ed(s): C. Dürr & T. Schwentick
Event: Symposium on Theoretical Aspects of Computer Science (STACS 2011) at Dortmund, Germany
Source: NC State University Libraries
Added: March 26, 2022
2011 chapter
The “Seven Dwarfs” of Symbolic Computation
In Texts & Monographs in Symbolic Computation (pp. 95–104).
TL;DR:
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, are presented.
(via Semantic Scholar)
Source: Crossref
Added: July 27, 2019
2010 conference paper
Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's method
Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation - ISSAC '10. Presented at the the 2010 International Symposium.
Event: the 2010 International Symposium
TL;DR:
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.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
10. Reduced Inequalities
(OpenAlex)
Source: Crossref
Added: August 18, 2019
2010 journal article
Efficiently Certifying Non-Integer Powers
COMPUTATIONAL COMPLEXITY, 19(3), 355–366.
author keywords: Integer roots; integer powers; linear-time algorithm; bit complexity; Chebotarev density theorem
TL;DR:
A randomized algorithm that, given an integer a, produces a certificate that the integer is not a pure power of an integer in expected (log a)1+o(1) bit operations under the assumption of the Generalized Riemann Hypothesis is described.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2010 conference paper
Fifteen years after DSC and WLSS2 what parallel computations I do today
Proceedings of the 4th International Workshop on Parallel and Symbolic Computation - PASCO '10. Presented at the the 4th International Workshop.
Event: the 4th International Workshop
TL;DR:
The paradigm of interactive symbolic supercomputing is proposed, a symbolic computation environment analog of the STAR-P Matlab platform, and multivariate sparse polynomial parallel interpolation constitutes a keystone operation, for which a new algorithm is presented.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2010 report
The Role of Symbolic, Numeric and Algebraic Computation in Cyber-Enabled Discovery and Innovation (CDI)
In Future Directions of Symbolic Computation Research And Their Applications to the Domain Sciences. University of Rhode Island.
Source: NC State University Libraries
Added: March 26, 2022
2009 conference paper
A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions
Proceedings of the 2009 conference on Symbolic numeric computation - SNC '09. Presented at the the 2009 conference.
Event: the 2009 conference
TL;DR:
Here a hybrid symbolic-numerical algorithm is applied for certifying that 4 polynomials can be written as an exact fraction of two polynomial sums-of-squares (SOS) with rational coefficients.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2008 conference paper
Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
Proceedings of the twenty-first international symposium on Symbolic and algebraic computation - ISSAC '08. Presented at the the twenty-first international symposium.
Event: the twenty-first international symposium
TL;DR:
This work generalizes the technique by Peyrl and Parillo to computing lower bound certificates for several well-known factorization problems in hybrid symbolic-numeric computation and certifies accurate rational lower bounds near the irrational global optima.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2008 conference paper
Expressing a fraction of two determinants as a determinant
Proceedings of the twenty-first international symposium on Symbolic and algebraic computation - ISSAC '08. Presented at the the twenty-first international symposium.
Event: the twenty-first international symposium
TL;DR:
The problem was motivated by resultant formulas derived from Chow forms and shows that divisions can be removed from formulas that compute polynomials in the input variables over a sufficiently large field within polynomial formula size growth.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2007 journal article
Approximate factorization of multivariate polynomials using singular value decomposition
JOURNAL OF SYMBOLIC COMPUTATION, 43(5), 359–376.
author keywords: multivariate polynomial factorization; approximate factorization; singular value decomposition; numerical algebra; Gauss-Newton optimization
TL;DR:
These 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.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2007 book
Computer algebra handbook foundations, applications, systems
Source: NC State University Libraries
Added: August 6, 2018
2007 journal article
Irreducible polynomials and barker sequences
ACM Communications in Computer Algebra, 41(4), 118.
TL;DR:
It is shown that in this case the problem can in fact be reduced to a question of irreducibility for a certain family of univariate polynomials, and it is proved that the polynmials in question are always reducible modulo <i>p</i>, for every prime.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2007 conference paper
Lower bounds for approximate factorizations via semidefinite programming
In J. Verschelde & S. M. Watt (Eds.), Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation (SNC '07) (pp. 203–204). New York, NY: ACM Press.
Ed(s): J. Verschelde & S. Watt
Event: International Workshop on Symbolic-Numeric Computation at London, Ontario, Canada on July 25-27, 2007
Source: NC State University Libraries
Added: March 26, 2022
2007 conference paper
On exact and approximate interpolation of sparse rational functions
ISSAC 2007: International Symposium for Symbolic and Algebraic Computation: Proceedings.
TL;DR:
Five new algorithms for 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 are presented and analyzed.
(via Semantic Scholar)
Source: NC State University Libraries
Added: August 6, 2018
2007 conference paper
On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms
International Workshop on Symbolic-Numeric Computation: Proceedings. New York: ACM Press.
Source: NC State University Libraries
Added: August 6, 2018
2007 chapter
Structured Low Rank Approximation of a Sylvester Matrix
In Trends in Mathematics (pp. 69–83).
author keywords: Sylvester matrix; approximate greatest common divisor; structured total least norm; hybrid symbolic/numeric algorithm
TL;DR:
This work presents iterative algorithms that compute an approximate GCD and that can certify an approximate ∈-GCD when a tolerance ∈ is given on input and demonstrates the practical performance of these algorithms on a diverse set of univariate pairs of polynomials.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2006 conference paper
Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials
Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06. Presented at the the 2006 international symposium.
Event: the 2006 international symposium
TL;DR:
This work presents an algorithm based on a version of the structured total least norm (STLN) method and demonstrates that the algorithm in practice computes globally minimal approximations on a diverse set of benchmark polynomials.
(via Semantic Scholar)
Source: Crossref
Added: August 18, 2019
2006 conference paper
Challenges in Symbolic Computation Software, number 06271
In Dagstuhl Seminar Proceedings. Germany: Schloss Dagstuhl.
Ed(s): W. Decker, M. Dewar, & S. Watt
Event: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI) at Schloss Dagstuhl
Source: NC State University Libraries
Added: March 26, 2022
2006 conference paper
Finding small degree factors of multivariate supersparse (lacunary) polynomials over algebraic number fields
Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06. Presented at the the 2006 international symposium.
Event: the 2006 international symposium
Source: Crossref
Added: August 28, 2020
2006 conference paper
Hybrid symbolic-numeric computation
Proceedings of the 2006 international symposium on Symbolic and algebraic computation - ISSAC '06. Presented at the the 2006 international symposium.
Event: the 2006 international symposium
TL;DR:
The focus of the 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2005 chapter
A note on the Risch differential equation
In J. Fitch (Ed.), EUROSAM 84 (pp. 359–366).
Ed(s): J. Fitch
Event: International Symposium on Symbolic and Algebraic Computation at Cambridge, England on July 9-11, 1984
TL;DR:
This paper relates to the technique of integrating a function in a purely transcendental regular elementary Liouville extension by prescribing degree bounds for the transcendentals and then solving linear systems over the constants.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
2005 chapter
Effective Hilbert irreducibility
In EUROSAM 84 (pp. 277–284).
Source: Crossref
Added: June 15, 2021
2005 chapter
Explicit construction of the hilbert class fields of imaginary quadratic fields with class numbers 7 and 11
In J. Fitch (Ed.), EUROSAM 84 (pp. 310–320).
Ed(s): J. Fitch
Event: International Symposium on Symbolic and Algebraic Computation at Cambridge, England on July 9-11, 1984
TL;DR:
This paper gives an explicit construction of the Hilbert class fields of some imaginary quadratic fields with class numbers 7 and 11 by explicitly evaluating the elliptic modular j -invariant at each representative of the ideal class of an imaginary Quadratic field, and forming the class equation.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
2005 conference paper
Generic matrix multiplication and memory management in linBox
Proceedings of the 2005 international symposium on Symbolic and algebraic computation - ISSAC '05. Presented at the the 2005 international symposium.
Event: the 2005 international symposium
TL;DR:
An interface mechanism that allows incorporation of external components with native memory management such as garbage collection into LinBox and an implementation of the interface based on SACLIB's field arithmetic procedures is presented.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2005 journal article
On the complexity of computing determinants
COMPUTATIONAL COMPLEXITY, 13(3-4), 91–130.
author keywords: integer matrix; matrix determinant; characteristic polynomial; Smith normal form; bit complexity; division-free complexity; randomized algorithm; multivariable control theory; realization; matrix sequence; block Wiedemann algorithm; block Lanczos algorithm
TL;DR:
New baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems 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 are presented.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2005 conference paper
On the complexity of factoring bivariate supersparse (Lacunary) polynomials
Proceedings of the 2005 international symposium on Symbolic and algebraic computation - ISSAC '05. Presented at the the 2005 international symposium.
Event: the 2005 international symposium
TL;DR:
Algorithms that compute linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size and it is shown that the problem of determining the irreducibility of a supersparse bivariatePolynomial over a large finite field of any characteristic is co-NP-hard via randomized reductions.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2005 chapter
Polynomial factorization 1987–1991
In Lecture Notes in Computer Science: Vol. 583. LATIN '92 (pp. 294–313).
Event: 1st Latin American Symposium on Theoretical Informatics at São Paulo, Brazil on April 6-10, 1992
TL;DR:
This article discusses important developments of the past five years in factorization and discusses the “classical univariate problems” of factoring a polynomial.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
2005 conference paper
Process scheduling in DSC and the large sparse linear systems challenge
Design and Implementation of Symbolic Computation Systems (DISCO 1993), 66–80.
Event: Design and Implementation of Symbolic Computation Systems International Symposium, DISCO '93 at Gmunden, Austria on September 15-17, 1993
TL;DR:
An algorithm is implemented that can prove a number of more than 1,000 decimal digits prime in about 2 months elapsed time on some 20 computers and a parallel version of a sparse linear system solver is used to compute the solution of sparse linear systems over finite fields.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
2004 conference paper
Approximate factorization of multivariate polynomials via differential equations
Proceedings of the 2004 international symposium on Symbolic and algebraic computation - ISSAC '04. Presented at the the 2004 international symposium.
Event: the 2004 international symposium
TL;DR:
It is demonstrated on a significant body of experimental data that the 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2004 journal article
Deterministic distinct-degree factorization of polynomials over finite fields
JOURNAL OF SYMBOLIC COMPUTATION, 38(6), 1461–1470.
author keywords: multivariate polynomial; deterministic algorithm; distinct-degree factorization
Source: Web Of Science
Added: August 6, 2018
2004 journal article
Early termination in Shoup's algorithm for the minimum polynomial of an algebraic
Source: NC State University Libraries
Added: March 26, 2022
2003 chapter
Absolute factorization of polynomials
In J. Grabmeier, E. Kaltofen, & V. Weispfenning (Eds.), Computer Algebra Handbook (p. 26). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: December 5, 2020
2003 article
Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
JOURNAL OF SYMBOLIC COMPUTATION, Vol. 36, pp. 401–424.
author keywords: sparse shifts; early termination; sparse polynomial; sparse interpolation; Chebyshev basis; Pochhammer basis
TL;DR:
These 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 earlytermination test.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2003 book
Computer Algebra Handbook
(J. Grabmeier, E. Kaltofen, & V. Weispfenning, Eds.). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: March 26, 2022
2003 chapter
Computer algebra - impact on research
In J. Grabmeier, E. Kaltofen, & V. Weispfenning (Eds.), Computer Algebra Handbook (pp. 4–6). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: December 5, 2020
2003 article
Computing the sign or the value of the determinant of an integer matrix, a complexity survey
Kaltofen, E., & Villard, G. (2004, January 1). JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, Vol. 162, pp. 133–146.
author keywords: determinant; bit-complexity; integer matrix; approximate computation; exact computation; randomized algorithms
TL;DR:
This work surveys the complexity of existing methods to solve problems when the input is an n × n matrix A with integer entries and studies the bit-complexities of the algorithms asymptotically in n and the norm of A.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2003 article
Early termination in sparse interpolation algorithms
JOURNAL OF SYMBOLIC COMPUTATION, Vol. 36, pp. 365–400.
author keywords: early termination; sparse polynomial; black box polynomial; interpolation; sparse interpolation; randomized algorithm
TL;DR:
Based on early termination, racing algorithms execute simultaneously dense and sparse algorithms that can be embedded as the univariate interpolation substep within Zippel's multivariate method.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2003 chapter
FoxBox and other blackbox systems
In J. Grabmeier, E. Kaltofen, & V. Weispfenning (Eds.), Computer Algebra Handbook (pp. 383–385). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: December 5, 2020
2003 chapter
Hybrid methods
In J. Grabmeier, E. Kaltofen, & V. Weispfenning (Eds.), Computer Algebra Handbook (pp. 112–125). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: December 5, 2020
2003 chapter
Linear systems
In J. Grabmeier, E. Kaltofen, & V. Weispfenning (Eds.), Computer algebra handbook: foundations, applications, systems (pp. 36–38). Heidelberg, Germany: Springer Verlag.
Ed(s): J. Grabmeier, & V. Weispfenning
Source: NC State University Libraries
Added: December 5, 2020
2003 conference paper
On approximate irreducibility of polynomials in several variables
Proceedings of the 2003 international symposium on Symbolic and algebraic computation - ISSAC '03. Presented at the the 2003 international symposium.
Event: the 2003 international symposium
TL;DR:
Using an absolute irreducibility criterion due to Ruppert, this work is able to find useful separation bounds, in several norms, for bivariate polynomials, and derive new, more effective Noether forms for polynmials of arbitrarily many variables.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2003 conference paper
Polynomial factorization
Proceedings of the 2003 international symposium on Symbolic and algebraic computation - ISSAC '03. Presented at the the 2003 international symposium.
Event: the 2003 international symposium
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2002 conference paper
'Using Maple to grade Maple' assessment software from North Carolina State University
Proceedings 2002 Maple Workshop. Waterloo, Canada: Waterloo Maple Inc. With Dmitriy Morozov, John May and William Turner.
Source: NC State University Libraries
Added: March 26, 2022
2002 conference paper
Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm
Proceedings of the 2002 international symposium on Symbolic and algebraic computation - ISSAC '02. Presented at the ISSAC 02: International symposium on symbolic and algebraic computation, Lille, France.
Event: ISSAC 02: International symposium on symbolic and algebraic computation at Lille, France
TL;DR:
A fraction-free version of the Berlekamp/Massey algorithm is given, which does not require rational numbers or functions and GCD operations on the arising numerators and denominators and is more efficient than the classical extended Euclidean algorithm.
(via Semantic Scholar)
Source: Crossref
Added: May 18, 2021
2002 conference paper
An output-sensitive variant of the baby steps/giant steps determinant algorithm
Proceedings of the 2002 international symposium on Symbolic and algebraic computation - ISSAC '02. Presented at the the 2002 international symposium.
Event: the 2002 international symposium
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2002 journal article
Efficient matrix preconditioners for black box linear algebra
LINEAR ALGEBRA AND ITS APPLICATIONS, 343, 119–146.
author keywords: black box matrix; sparse matrix; structured matrix; Toeplitz-like matrix; matrix preconditioner; exact arithmetic; finite field; symbolic computation; linear system solution; minimal polynomial; characteristic polynomial; rank; determinant; Wiedemann algorithm; randomized algorithm; butterfly network
TL;DR:
Improvements are offered for the efficiency and applicability of preconditioners on linear algebra problems over finite fields, but most results are valid for entries from arbitrary fields.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2002 conference paper
LINBOX: A GENERIC LIBRARY FOR EXACT LINEAR ALGEBRA
Mathematical Software. Presented at the Proceedings of the First International Congress of Mathematical Software.
Event: Proceedings of the First International Congress of Mathematical Software
TL;DR:
The design of this generic library LinBox is described, its current range of capabilities are sketched, its guiding design principle of re-usability is given, and several examples of its use are given.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
2001 conference paper
Algorithms for sparse and black box matrices over finite fields
Kaltofen, E. (2001, May 23). Presented at the International Conference on Finite Fields and Applications, Oaxaca, Mexico.
Event: International Conference on Finite Fields and Applications at Oaxaca, Mexico
Source: NC State University Libraries
Added: March 26, 2022
2000 review
Challenges of symbolic computation: My favorite open problems
[Review of ]. JOURNAL OF SYMBOLIC COMPUTATION, 29(6), 891–919.
TL;DR:
The author presents background to each of his problems and a clear-cut test that evaluates whether a proposed attack has solved one of my problems, and state his favorite eight open problems in symbolic computation.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
2000 conference paper
Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
Proceedings of the 2000 international symposium on Symbolic and algebraic computation symbolic and algebraic computation - ISSAC '00. Presented at the the 2000 international symposium.
Event: the 2000 international symposium
Source: Crossref
Added: August 28, 2020
1999 journal article
Distributed matrix-free solution of large sparse linear systems over finite fields
ALGORITHMICA, 24(3-4), 331–348.
author keywords: distributed symbolic computation; sparse linear systems; block Wiedemann; outer loop parallelization
TL;DR:
An outer loop parallelization that works well in conjunction with a black box abstraction for the coefficient matrix is performed that can be run on a network cluster of UNIX workstations as well as on an SP-2 multiprocessor.
(via Semantic Scholar)
Source: Web Of Science
Added: August 6, 2018
1999 journal article
East Coast Computer Algebra Day '99 (April 24, 1999): Abstracts of invited talks and presented posters
Association for Computing Machinery SIGSAM Bulletin, 33(2), 43–52.
Ed(s): H. Hong n, n & M. Singer n
Event: East Coast Computer Algebra Day on April 24, 1999
TL;DR:
All photographs courtesy of Hoon Hong Erich Kaltofen, Michael Singer and Michael Singer.
(via Semantic Scholar)
Source: NC State University Libraries
Added: March 26, 2022
1999 conference paper
Efficient algorithms for computing the nearest polynomial with a real root and related problems
Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99. Presented at the the 1999 international symposium.
Event: the 1999 international symposium
TL;DR:
Three new algorithms in the general area of input-sensitivity analysis are presented: a problem formulation, possibly with floating point coefficients, lacks an expected property because the inputs are slightly perturbed, and a task is to efficiently compute the nearest problem that has the desired property.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1999 conference paper
On the genericity of the modular polynomial GCD algorithm
Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99. Presented at the the 1999 international symposium.
Event: the 1999 international symposium
TL;DR:
This paper develops the algorithm for multivariate polynomials over Euclidean domains which have a special kind of remainder function and applies this generic algorithm to a GCD problem in Z/(p)[t][x] where p is small, yielding an improved asymptotic performance over the usual approach.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1999 conference paper
Symbolic computation in Java
Proceedings of the 1999 international symposium on Symbolic and algebraic computation - ISSAC '99. Presented at the the 1999 international symposium.
Event: the 1999 international symposium
TL;DR:
This article discusses Java as a symbolic computation development tool, expanding on the pioneering efforts of other researchers and investigates if Java can compete with C++, or Maple/Mathematica/Axiom for efficient programming.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1998 chapter
Algebraic Algorithms
In Algorithms and Theory of Computation Handbook.
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: January 21, 2021
1998 conference paper
Efficient algorithms for computing the nearest polynomial with constrained roots
Proceedings of the 1998 international symposium on Symbolic and algebraic computation - ISSAC '98. Presented at the the 1998 international symposium.
Event: the 1998 international symposium
TL;DR:
This work gives a polynomial-time algorithm to compute the radius of stability in the Euclidean norm for a variety of stability domains and develops hybrid symbolic-numeric algorithms to constrain one root of a complex or realPolynomial to a curve in the complex plane.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1998 conference paper
FOXBOX
Proceedings of the 1998 international symposium on Symbolic and algebraic computation - ISSAC '98. Presented at the the 1998 international symposium.
Event: the 1998 international symposium
TL;DR:
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 is introduced and the results of several challenge problems are presented, representing the first symbolic solutions of such problems.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1998 journal article
Subquadratic-time factoring of polynomials over finite fields
MATHEMATICS OF COMPUTATION, 67(223), 1179–1197.
author keywords: factoring; polynomials; finite fields; randomized algorithms; normal bases
Source: Web Of Science
Added: August 6, 2018
1997 chapter
Algebraic algorithms
In A. B. Tucker (Ed.), The computer science and engineering handbook (pp. 226–248). Boca Raton, Florida: CRC Press.
Ed(s): A. Tucker
Source: NC State University Libraries
Added: March 26, 2022
1997 conference paper
Fast polynomial factorization over high algebraic extensions of finite fields
Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC '97. Presented at the the 1997 international symposium.
Event: the 1997 international symposium
TL;DR:
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, and these algorithms are asymptotically faster than previous known algorithms.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1997 conference paper
On randomized Lanczos algorithms
Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC '97. Presented at the the 1997 international symposium.
Event: the 1997 international symposium
TL;DR:
Las Vegas algorithms that are based on Lanczos’s method for solving symmetric linear systems are presented and analyzed and suggest that these Lanczos algorithms are preferable to several versions of Wiedemann's method for computations over large fields, especially for certain symmetric matrix computations.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1997 book
PASCO '97: Proceedings of the second international symposium on Parallel symbolic computation
Ed(s): H. Hong, & M. Hitz
Event: PASCO97: International Symposium on Parallel Symbolic Computation at Maui, Hawaii on July 20-22, 1997
Source: Crossref
Added: June 15, 2021
1997 journal article
Teaching computational abstract algebra
JOURNAL OF SYMBOLIC COMPUTATION, 23(5-6), 503–515.
TL;DR:
The topics covered and the didactical use of the corresponding Mathematica packages were described, as well as conclusions for future such courses from the students' comments and their own experience.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
4. Quality Education
(OpenAlex)
Source: Web Of Science
Added: August 6, 2018
1996 conference paper
Blocked iterative sparse linear system solvers for finite fields
In C. Roucairol (Ed.), Proceedings of the Symposium of Parallel Computing Solving Large Scale Irregular Applications (Stratagem '96) (pp. 91–95). Sophia Antipolis, France: INRIA.
Ed(s): C. Roucairol
Source: NC State University Libraries
Added: March 26, 2022
1996 conference paper
Generic Gram-Schmidt orthogonalization by exact division
Proceedings of the 1996 international symposium on Symbolic and algebraic computation - ISSAC '96. Presented at the the 1996 international symposium.
Event: the 1996 international symposium
TL;DR:
This paper develops and shows how to express generic algorithms in C+so that all three possibilities are available using a single source code, and takes advantage of the genericness to test and time the algorithm using different arithmetics, including three huge-integer arithmetic packages.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1996 conference paper
On rank properties of Toeplitz matrices over finite fields
Proceedings of the 1996 international symposium on Symbolic and algebraic computation - ISSAC '96. Presented at the the 1996 international symposium.
Event: the 1996 international symposium
TL;DR:
These statements are proven with the extended Euclidean algorithm and the theory of subresultants that a matrix has generic rank r when all its leading principal minors up to dimension r are non-zero, and r is maximal.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1996 chapter
Prediction Based Task Scheduling in Distributed Computing
In Languages, Compilers and Run-Time Systems for Scalable Computers (pp. 317–320).
Source: Crossref
Added: August 28, 2020
1995 journal article
Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems
Mathematics of Computation, 64(210), 777–777.
Source: Crossref
Added: August 28, 2020
1995 journal article
Effective Noether Irreducibility Forms and Applications
Journal of Computer and System Sciences, 50(2), 274–295.
Source: Crossref
Added: August 28, 2020
1995 journal article
Integer division in residue number systems
IEEE Transactions on Computers, 44(8), 983–989.
author keywords: INTEGER DIVISION; RECIPROCAL; NEWTON ITERATION; EXTENDED RESIDUE NUMBER SYSTEM; MIXED RADIX CONVERSION; BASE EXTENSION
TL;DR:
This contribution to the ongoing discussion of division algorithm for residue number systems (RNS) is based on Newton iteration for computing the reciprocal, and an extended RNS with twice the number of moduli provides the range required for multiplication and scaling.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1995 conference paper
On computing greatest common divisors with polynomials given by black boxes for their evaluations
In A. H. M. Levelt (Ed.), Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95.
Ed(s): A. Levelt
Event: ISSAC95: International Symposium on Symbolic and Algebraic Computation at Montreal Quebec Canada on July 10-12, 1995
TL;DR:
This work revisits the problem of computing the greatest common divisor (GCD) in black box format of several multivariate polynomials that themselves are given by black boxes and presents an improved version of the algorithm sketched in Kaltofen and Trager.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1995 journal article
Process Scheduling in DSC and the Large Sparse Linear Systems Challenge
Journal of Symbolic Computation, 19(1-3), 269–282.
Source: Crossref
Added: August 28, 2020
1994 chapter
A Distributed Approach to Problem Solving in Maple
In Maple V: Mathematics and its Applications (pp. 13–21).
TL;DR:
A system is described whereby a Maple computation can be distributed across a network of computers running Unix, 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1994 conference paper
Asymptotically fast solution of Toeplitz-like singular linear systems
Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. Presented at the the international symposium.
Event: the international symposium
TL;DR:
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 is considered and it is shown that if the system is solvable the authors 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1994 conference paper
Factoring high-degree polynomials by the black box Berlekamp algorithm
Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. Presented at the the international symposium.
Event: the international symposium
Source: Crossref
Added: August 28, 2020
1994 conference paper
Parallel solution of Toeplitz and Toeplitz-like linear systems over fields of small positive characteristic
In H. Hong (Ed.), Proceedings of the First International Symposium of Parallel Symbolic Computation (pp. 225–233). Singapore: World Scientific Publishing Co.
Ed(s): H. Hong
Source: NC State University Libraries
Added: March 26, 2022
1993 chapter
Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems
In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (pp. 195–212).
TL;DR:
It is proved 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1993 report
Computational differentiation and algebraic complexity theory
In C. H. Bischof, A. Griewank, & P. M. Khademi (Eds.), Workshop Report on First Theory Institute on Computational Differentiation (Technical Report No. ANL/MCS-TM-183; pp. 28–30). Argonne, Illinois: Argonne National Laboratory.
Ed(s): C. Bischof, A. Griewank & P. Khademi
Source: NC State University Libraries
Added: March 26, 2022
1993 journal article
Direct proof of a theorem by Kalkbrener, Sweedler, and Taylor
ACM SIGSAM Bulletin, 27(4), 2.
TL;DR:
This note presents a direct proof of the following fact: Kalkbrener, Sweedler, and Taylor (1993) present degree bounds on the coefficients needed to express 1 (and other low degree polynomials) asigma.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1993 chapter
Dynamic parallel evaluation of computation DAGs
In J. Reif (Ed.), Synthesis of Parallel Algorithms (pp. 723–758). San Mateo, California: Morgan Kaufmann Publishers.
Ed(s): J. Reif
Source: NC State University Libraries
Added: March 26, 2022
1992 report
Efficient solution of sparse linear systems
[Lecture Notes]. Troy, New York: Rensselaer Polytechnic Institute, Department of Computer Science.
Source: NC State University Libraries
Added: March 26, 2022
1992 conference paper
On computing determinants of matrices without divisions
Papers from the international symposium on Symbolic and algebraic computation - ISSAC '92. Presented at the Papers from the international symposium.
Event: Papers from the international symposium
TL;DR:
An algorithm 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1992 conference paper
Processor-efficient parallel solution of linear systems. II. The positive characteristic and singular cases
Proceedings., 33rd Annual Symposium on Foundations of Computer Science. Presented at the Proceedings., 33rd Annual Symposium on Foundations of Computer Science.
Event: Proceedings., 33rd Annual Symposium on Foundations of Computer Science
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1991 conference paper
DSC: a system for distributed symbolic computation
In S. M. Watt (Ed.), Proceedings of the 1991 international symposium on Symbolic and algebraic computation - ISSAC '91 (pp. 323–332).
Ed(s): S. Watt
Event: ISSAC 91: International Symposium on Symbolic Algebraic Computation at Bonn, West Germany on July 15-17, 1991
TL;DR:
This work has 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.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1991 conference paper
Effective Noether irreducibility forms and applications
Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91. Presented at the the twenty-third annual ACM symposium.
Event: the twenty-third annual ACM symposium
TL;DR:
The “single path lazy factorization” representation model for elements in algebraic extension fields is introduced, with which the problem of factoring polynomials with rational number or rational function coefficients can be solved within the parallel computational complexity class MC.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1991 chapter
Explicit Construction of the Hilbert Class Fields of Imaginary Quadratic Fields by Integer Lattice Reduction
In D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn, & M. B. Nathanson (Eds.), Number Theory (pp. 149–202).
Ed(s): D. Chudnovsky, G. Chudnovsky, H. Cohn & M. Nathanson
Source: Crossref
Added: June 15, 2021
1991 journal article
On fast multiplication of polynomials over arbitrary algebras
Acta Informatica, 28(7), 693–701.
TL;DR:
This paper generalizes the well-known Sch6nhage-Strassen algorithm for multiplying large integers to an algorithm for dividing polynomials with coefficients from an arbitrary, not necessarily commutative, not always associative, algebra d, and obtains a method not requiring division that is valid for any algebra.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1991 chapter
On wiedemann's method of solving sparse linear systems
In H. F. Mattson, T. Mora, & T. R. N. Rao (Eds.), Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (pp. 29–38).
Ed(s): H. Mattson, T. Mora & T. Rao
Event: 9th International Symposium, AAECC-9 at New Orleans, LA on October 7-11, 1991
TL;DR:
Douglas Wiedemann’s (1986) landmark approach to solving sparse linear systems over finite fields provides the symbolic counterpart to non-combinatorial numerical methods for solving sparselinear systems, such as the Lanczos or conjugate gradient method.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1991 conference paper
Processor efficient parallel solution of linear systems over an abstract field
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures - SPAA '91. Presented at the the third annual ACM symposium.
Event: the third annual ACM symposium
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1991 conference paper
Size efficient parallel algebraic circuits for partial derivatives
In D. V. Shirkov, V. A. Rostovtsev, & V. P. Gerdt (Eds.), IV International Conference on Computer Algebra in Physical Research (pp. 133–145). Singapore: World Scientific Publishing Co.
Ed(s): D. Shirkov, V. Rostovtsev & V. Gerdt
Source: NC State University Libraries
Added: March 26, 2022
1990 journal article
Algebraic Computational Complexity
Journal of Symbolic Computation, 9(3).
Ed(s):
Source: NC State University Libraries
Added: March 26, 2022
1990 conference paper
Computer mathematics systems and a trilateral approach to human resource development in technical occupations
In N. Estes, J. Heene, & D. Leclercq (Eds.), Proceedings of the 7th International Conference on Technology and Education (Vol. 1, pp. 251–253). Edinburgh, United Kingdom: CEP Consultants Ltd.
Ed(s): N. Estes, J. Heene & D. Leclercq
Source: NC State University Libraries
Added: March 26, 2022
1990 journal article
Computing the irreducible real factors and components of an algebraic curve
Applicable Algebra in Engineering, Communication and Computing, 1(2), 135–148.
TL;DR:
These algorithms are of polynomial bit complexity in the degree of the equation and the size of its coefficients and are based on computing the irreducible complex factors and then investigating high precision complex floating point coefficients of these factors and the complex norms.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1990 journal article
Computing with polynomials given byblack boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators
Journal of Symbolic Computation, 9(3), 301–320.
Source: Crossref
Added: January 24, 2021
1990 conference paper
Modular rational sparse multivariate polynomial interpolation
Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '90. Presented at the the international symposium.
Event: the international symposium
TL;DR:
The computing times for the speeded Ben-Or and Tiwari and the modular algorithm are compared, and it is shown that the modular algorithms is markedly superior.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1990 journal article
Parallel algorithms for matrix normal forms
Linear Algebra and Its Applications, 136, 189–208.
TL;DR:
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 that is probabilistic of Las Vegas type and reduces the problem of Smith form computation to two Hermite form computations.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1990 chapter
Polynomial factorization 1982-1986
In D. V. Chudnovsky & R. D. Jenks (Eds.), Computers in Mathematics, Lecture Notes in Pure and Applied Mathematics (Vol. 125, pp. 285–309). New York, NY: Marcel Dekker, Inc.
Ed(s): D. Chudnovsky & R. Jenks
Source: NC State University Libraries
Added: March 26, 2022
1989 conference paper
An improved Las Vegas primality test
Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89. Presented at the the ACM-SIGSAM 1989 international symposium.
Event: the ACM-SIGSAM 1989 international symposium
TL;DR:
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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1989 book
Computers and Mathematics
Ed(s): * & S. Watt
TL;DR:
This volume contains the contributed papers accepted for presentation, selected from 85 drafts submitted in response to the call for papers.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1989 journal article
Computing greatest common divisors and factorizations in quadratic number fields
Mathematics of Computation, 53(188), 697–697.
TL;DR:
It is shown 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1989 conference paper
Computing the irreducible real factors and components of an algebraicf curve
In K. Mehlhorn (Ed.), Proceedings of the fifth annual symposium on Computational geometry - SCG '89 (pp. 79–87).
Ed(s): K. Mehlhorn
Event: Fifth annual symposium on Computational geometry
Source: Crossref
Added: June 15, 2021
1989 chapter
Factorization of polynomials given by straight-line programs
In S. Micali (Ed.), Randomness and Computation, Advances in Computing Research (Vol. 5, pp. 375–412). Greenwhich, Connecticut: JAI Press Inc.
Ed(s): S. Micali
Source: NC State University Libraries
Added: March 26, 2022
1989 chapter
Improved sparse multivariate polynomial interpolation algorithms
In Symbolic and Algebraic Computation (pp. 467–474).
Event: International Symposium ISSAC '88 at Rome, Italy on July 4-8, 1988
TL;DR:
This work considers the problem of interpolating sparse multivariate polynomials from their values and presents 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.
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1989 chapter
Mr. Smith goes to Las Vegas: Randomized parallel computation of the Smith Normal form of polynomial matrices
In Lecture Notes in Computer Science (pp. 317–322).
TL;DR:
The 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1989 conference paper
Parallel algebraic algorithm design
Kaltofen, E. (1989, July). Presented at the 1989 International Symposium on Symbolic and Algebraic Computation, Portland, Oregon.
Event: 1989 International Symposium on Symbolic and Algebraic Computation at Portland, Oregon
Source: NC State University Libraries
Added: March 26, 2022
1989 conference paper
Solving systems of nonlinear polynomial equations faster
Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation - ISSAC '89. Presented at the the ACM-SIGSAM 1989 international symposium.
Event: the ACM-SIGSAM 1989 international symposium
TL;DR:
This paper considers projective problems, that is, the polynomials are homogeneous and the solutions are sought in n-dimensional projective space, and shows that the solutions of an affine system are specializations of the solution rays of its homogenized projective version.
(via Semantic Scholar)
Source: Crossref
Added: January 24, 2021
1988 journal article
Analysis of the binary complexity of asymptotically fast algorithms for linear system solving
ACM SIGSAM Bulletin, 22(2), 41–49.
TL;DR:
Two significant developments can be distinguished in the theory of algebraic algorithm design: that of fast algorithms in terms of counting the arithmetic operations, and the actual bit complexity when such algorithms are performed for concrete fields, in particular the rational numbers.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1988 conference paper
Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. Presented at the [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science.
Event: [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
TL;DR:
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, and 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 polynometric time.
(via Semantic Scholar)
UN Sustainable Development Goal Categories
4. Quality Education
(OpenAlex)
Source: Crossref
Added: August 28, 2020
1988 journal article
Dagwood: a system for manipulating polynomials given by straight-line programs
ACM Transactions on Mathematical Software, 14(3), 218–240.
TL;DR:
This work discusses the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations capable of performing rational arithmetic on, evaluating, differentiating, taking greatest common divisors of, and factoring polynomials instraight-line format.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1988 journal article
Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
SIAM Journal on Computing, 17(4), 687–695.
TL;DR:
A new parallel algorithm is given to evaluate a straight line 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.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1988 journal article
Greatest common divisors of polynomials given by straight-line programs
Journal of the ACM, 35(1), 231–264.
TL;DR:
It is shown that most algebraic algorithms can be probabilistically applied to data that are given by a straight-line computation, and every degree-bounded rational function can be computed fast in parallel, that is, in polynomial size and polylogarithmic depth.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1987 journal article
Computer Algebra Algorithms
Annual Review of Computer Science, 2(1), 91–118.
TL;DR:
A systematic review of Integer and Polynomial Addition, Multiplication, and Division with Remainder and its applications in Language and System Design and Decision Methods for Elementary Algebr a and Geometry.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1987 journal article
Deterministic irreducibility testing of polynomials over large finite fields
Journal of Symbolic Computation, 4(1), 77–82.
TL;DR:
This work presents a sequential deterministic polynomial-time algorithm for testing dense multivariate polynomials over a large finite field for irreducibility, based on the algorithm for absolute irreduceibility testing combined with Berlekamp's algorithm.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1987 journal article
Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices
SIAM Journal on Algebraic Discrete Methods, 8(4), 683–690.
TL;DR:
A polynomial-time deterministic sequential algorithm for the Smith normal form over the rationals, which is applied to the rational canonical form of matrices over finite fields and the field of rational numbers.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1987 report
Fast multiplication of polynomials over arbitrary rings
(Technical Report No. 87-35). Troy, NY: Rensselaer Polytechnic Institute, Department of Computer Science.
Source: NC State University Libraries
Added: March 26, 2022
1987 conference paper
Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials
Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87. Presented at the the nineteenth annual ACM conference.
Event: the nineteenth annual ACM conference
TL;DR:
Three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given bystraight-line programs of unbounded input degree, and a higher order partial derivative in a single variable is shown.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1986 conference paper
A system for manipulating polynomials given by straight-line programs
Proceedings of the fifth ACM symposium on Symbolic and algebraic computation - SYMSAC '86. Presented at the the fifth ACM symposium.
Event: the fifth ACM symposium
TL;DR:
This work discusses the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations capable of performing rational arithmetic, evaluating, differentiating, taking greatest common divisors of, and factoring polynomials instraight-line format.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1986 chapter
Efficient parallel evaluation of straight-line code and arithmetic circuits
In VLSI Algorithms and Architectures (pp. 236–245).
Source: Crossref
Added: August 28, 2020
1986 conference paper
Fast parallel algorithms for similarity of matrices
Proceedings of the fifth ACM symposium on Symbolic and algebraic computation - SYMSAC '86. Presented at the the fifth ACM symposium.
Event: the fifth ACM symposium
Source: Crossref
Added: August 28, 2020
1986 conference paper
Uniform closure properties of P-computable functions
Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86. Presented at the the eighteenth annual ACM symposium.
Event: the eighteenth annual ACM symposium
TL;DR:
The question of whether pcomputable families would be closed under natural mathematics operations was raised and it was shown that by taking repeated part ial derivatives in a single variable one can obtain the general permanent from a polynomial-sized formula.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 conference paper
Computing with polynomials given by straight-line programs I: greatest common divisors
Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85. Presented at the the seventeenth annual ACM symposium.
Event: the seventeenth annual ACM symposium
TL;DR:
This work develops algorithms on multivariate polynomials represented by straight-line programs for the greatest common divisor problem and conversion to sparse representation and in random polynomial-time for the usual coefficient fields and output.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 conference paper
Computing with polynomials given by straight-line programs II sparse factorization
26th Annual Symposium on Foundations of Computer Science (sfcs 1985). Presented at the 26th Annual Symposium on Foundations of Computer Science (sfcs 1985).
Event: 26th Annual Symposium on Foundations of Computer Science (sfcs 1985)
TL;DR:
An algorithm for the factorization of a multivariate polynomial represented by a straight-line program into its irreducible factors represented as sparse polynomials is developed with controllably high probability the correct factorization.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 journal article
Effective Hilbert irreducibility
Information and Control, 66(3), 123–137.
TL;DR:
A probabilistic irreducibility test for sparse multivariate poly omials over arbitrary perfect fields is constructed using a very effective version of the Hilbert Irreducible-n Theorem.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 journal article
Factoring sparse multivariate polynomials
Journal of Computer and System Sciences, 31(2), 265–287.
TL;DR:
A probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field, based on an effective version of Hilbert's irreducibility theorem is presented.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 journal article
Factorization of multivariate polynomials over finite fields
Mathematics of Computation, 45(171), 251–251.
TL;DR:
A probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in timePolynomial in the input size, i.e., in the degree of the polynomials and log (cardinality of field).
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1985 journal article
Fast parallel absolute irreducibility testing
Journal of Symbolic Computation, 1(1), 57–67.
TL;DR:
It is established that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth and also to the class of sequentiallyPolynomial-time problems.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 journal article
Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
SIAM Journal on Computing, 14(2), 469–489.
TL;DR:
An algorithm is presented 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 polynomials, which implies the following theorem.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 chapter
Sparse hensel lifting
In EUROCAL '85 (pp. 4–17).
TL;DR:
It is shown how the content of the input polynomial in the main variable as a by-product can be taken advantage of when computing the GCD of multivariate polynomials by sparse Hensel lifting.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1985 report
The integer manipulation techniques can compete with the linear algebra methods for solving sparse linear systems
(Technical Report No. 85-6). State University of New York at Albany, Computer Science Department.
Source: NC State University Libraries
Added: March 26, 2022
1984 chapter
On a theorem by R. Dedekind
In H. W. Lenstra Jr., J. K. Lenstra, & P. van Emde Boas (Eds.), DOPO LE PAROLE, Album in Honor of A. K. Lenstra's Doctorate. Amsterdam.
Ed(s): H. Lenstra, J. Lenstra & P. van Emde Boas
Source: NC State University Libraries
Added: March 26, 2022
1984 report
The algebraic theory of integration
[Lecture Notes]. Troy, New York: Rensselaer Polytechnic Institute, Department of Computer Science.
Source: NC State University Libraries
Added: March 26, 2022
1984 conference paper
The modular equation of order 11
Third Macsyma Users' Conference, 472–485. General Electric.
Source: NC State University Libraries
Added: March 26, 2022
1983 journal article
A Generalized Class of Polynomials that are Hard to Factor
SIAM Journal on Computing, 12(3), 473–483.
Source: Crossref
Added: August 28, 2020
1983 chapter
On the complexity of finding short vectors in integer lattices
In Lecture Notes in Computer Science (pp. 236–244).
TL;DR:
It is proved that this algorithm can actually be executed in O(n6(log B)2+n5( log B)3) binary steps by analyzing a modified version of the algorithm which also performs better in practice.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1983 chapter
Polynomial-time factorization of multivariate polynomials over finite fields
In Lecture Notes in Computer Science: Vol. 154. Automata, Languages and Programming (pp. 250–263).
Event: 10th Colloquium at Barcelona, Spain on July 18-22, 1983
TL;DR:
A probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in timePolynomial in the input size, i.e. in the degree of the polynomials and log (cardinality of field).
(via Semantic Scholar)
Source: Crossref
Added: June 15, 2021
1982 conference paper
A polynomial reduction from multivariate to bivariate integral polynomial factorization.
Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. Presented at the the fourteenth annual ACM symposium.
Event: the fourteenth annual ACM symposium
TL;DR:
It is shown 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 polynmials for irReducibility.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1982 conference paper
A polynomial-time reduction from bivariate to univariate integral polynomial factorization
23rd Annual Symposium on Foundations of Computer Science (sfcs 1982). Presented at the 23rd Annual Symposium on Foundations of Computer Science.
Event: 23rd Annual Symposium on Foundations of Computer Science
Source: Crossref
Added: August 28, 2020
1982 chapter
Factorization of Polynomials
In B. Buchberger, G. E. Collins, & R. Loos (Eds.), Computing Supplementum (pp. 95–113).
Ed(s): B. Buchberger, G. Collins & R. Loos
Source: Crossref
Added: June 15, 2021
1982 thesis
On the complexity of factoring polynomials with integer coefficients
(PhD thesis). Rensselaer Polytechnic Institute, Troy, NY.
Source: NC State University Libraries
Added: March 26, 2022
1981 conference paper
A generalized class of polynomials that are hard to factor
Proceedings of the fourth ACM symposium on Symbolic and algebraic computation - SYMSAC '81. Presented at the the fourth ACM symposium.
Event: the fourth ACM symposium
TL;DR:
A class of univariate polynomials is defined which make the Berlekamp-Hensel factorization algorithm take an exponential amount of time.
(via Semantic Scholar)
Source: Crossref
Added: August 28, 2020
1981 report
An attributed LL(1) compilation of Pascal into the lambda-calculus
(Technical Report No. CS-8103). Troy, NY: Rensselaer Polytechnic Institute Mathematical Sciences Department.
Source: NC State University Libraries
Added: March 26, 2022
1980 report
LISP/370 under the Michigan Terminal System
Troy, NY: Rensselaer Polytechnic Institute, Mathematical Sciences Department.
Source: NC State University Libraries
Added: March 26, 2022
Citation Index includes data from a number of different sources. If you have questions about the sources of data in the Citation Index or need a set of data which is free to re-distribute, please contact us.
Certain data included herein are derived from the Web of Science© and InCites© (2024) of Clarivate Analytics. All rights reserved. You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.