research-article

Challenges of Symbolic Computation

Author:

Erich KaltofenAuthors Info & Claims

Journal of Symbolic Computation, Volume 29, Issue 6

Pages 891 - 919

https://doi.org/10.1006/jsco.2000.0370

Published: 01 June 2000 Publication History

Abstract

The success of the symbolic mathematical computation discipline is striking. The theoretical advances have been continuous and significant: Gr bner 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.

References

[1]

S. K. Abdali, G. W. Cherry, N. Soiffer, Proceedings of the 1986 Symposium on Symbolic Algebraic Computation, Symsac ¿86, Char, B. W. 1986, ACM, New York, 24, 30

[2]

N.I. Achiezer, Frederick Ungar Publ. Co, New York, 1956.

[3]

M. Ajtai, C. Dwork, Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, 1997, ACM Press, New York, 284, 293

[4]

A. Antoniou, McGraw-Hill Book Co, New York, 1979.

[5]

L. Babai, 1979, Univ. de Montréal, Dép. de mathématiques et de statistique

[6]

L. Babai, On Lovász lattice reduction and the nearest lattice point problem, Combinatorica, 6 (1986) 1-13.

Digital Library

[7]

O. Bachmann, H. Schönemann, S. Gray, pp. 165, 175

[8]

D. Bailey, P. Borwein, S. Plouffe, On the rapid computation of various polylogarithmic constants, Math. Comput., 66 (1997) 903-913.

Digital Library

[9]

T. Becker, V. Weispfenning, Springer Verlag, New York, 1993.

[10]

E.R. Berlekamp, Factoring polynomials over large finite fields, Math. Comput., 24 (1970) 713-735.

[11]

L. Bernardin, B. Char, E. Kaltofen, pp. 237, 244

[12]

D.J. Bernstein, Composing power series over a finite ring in essentially linear time, J. Symb. Comput., 26 (1998) 339-341.

Digital Library

[13]

R.B. Boppana, R. Hirschfeld, Pseudorandom generators and complexity classes, in: Randomness and Computation, JAI Press Inc, Greenwhich, Connecticut, 1989, pp. 1-26.

[14]

J. M. Borwein, P. Lison¿k

[15]

R.P. Brent, F.G. Gustavson, D.Y.Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1 (1980) 259-295.

[16]

M. Bronstein, Springer Verlag, 1997.

[17]

W.S. Brown, On Euclid¿s algorithm and the computation of polynomial greatest common divisors, J. ACM, 18 (1971) 478-504.

Digital Library

[18]

W.S. Brown, J.F. Traub, On Euclid¿s algorithm and the theory of subresultants, J. ACM, 18 (1971) 505-514.

Digital Library

[19]

B. Buchberger, 1965

[20]

B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes Math., 4 (1970) 374-383.

[21]

B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, in: Recent Trends in Multidimensional Systems Theory, D. Reidel Publ. Comp, Dordrecht (Holland), 1985, pp. 184-232.

[22]

P. Bürgisser, M. Clausen, M.A. Shokrollahi, Springer Verlag, Heidelberg, Germany, 1997.

[23]

J. Canny, Generalized characteristic polynomials, J. Symb. Comput., 9 (1990) 241-250.

Digital Library

[24]

J. Canny, E. Kaltofen, L. Yagati, Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic Algebraic Computation, ISSAC ¿89, 1989, ACM, 121, 128

[25]

C. Carathéodory, Chelsea, New York, 1964.

[26]

B.F. Caviness, J.R., eds Johnson, Springer Verlag, Berlin/Heidelberg, 1998.

[27]

G.E. Collins, A method for overlapping and erasure of lists, Commun. ACM, 3 (1960) 655-657.

Digital Library

[28]

R. M. Corless, P. M. Gianni, B. M. Trager, S. M. Watt, pp. 96, 103

[29]

R.M. Corless, D.J. Jeffrey, The unwinding number, SIGSAM Bull., 30 (1996) 28-35.

Digital Library

[30]

D. Cox, J. Little, D. O¿Shea, Springer, New York, 1996.

[31]

S. Dalmas, M. Gaëtano, S. Watt

[32]

A. D¿́az, E. Kaltofen, pp. 30, 37

[33]

A. Dingle, R. Fateman, ISSAC ¿94, Proceedings of the International Symposium on Symbolic Algebraic Computation, 1994, 250, 257

[34]

S, ed. Dooley, ISSAC ¿99, Proceedings of the 1999 International Symposium on Symbolic Algebraic Computing, 1999, ACM Press, New York

[35]

W. Eberly, E. Kaltofen, pp. 176, 183

[36]

C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika, 1 (1936) 211-218.

[37]

I.Z. Emiris, A. Galligo, H. Lombardi, Certified approximate univariate GCDs, J. Pure Appl. Algebra, 117 & 118 (1997) 229-251.

[38]

I. Z. Emiris, V. Y. Pan, pp. 189, 196

[39]

M. J. Encarnación, pp. 265, 270

[40]

J.-C. Faugère

[41]

H. R. P. Ferguson, D. H. Bailey, 1996, NASA Ames Research Center

[42]

C.M. Fiduccia, On obtaining upper bounds on the complexity of matrix multiplication, in: Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 31-40.

[43]

C. M. Fiduccia, 1973

[44]

A. Galligo, S. Watt, pp. 217, 224

[45]

F.R. Gantmacher, Chelsea Publ. Co, New York, 1960.

[46]

J. von zur Gathen, J. Gerhard, Cambridge University Press, Cambridge, 1999.

[47]

J. von zur Gathen, V. Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity, 2 (1992) 187-224.

[48]

M. Giesbrecht, pp. 1, 10

[49]

M. Giesbrecht, A. Lobo, B. D. Saunders, pp. 113, 119

[50]

O, ed. Gloor, ISSAC 98, Proceedings of the International Symposium on Symbolic Algebraic Computation, 1998, ACM Press, New York

[51]

O. Goldreich, S. Goldwasser, S. Halevi, pp. 103, 111

[52]

O. Goldreich, S. Goldwasser, S. Halevi, pp. 112, 131

[53]

G.H. Golub, C.F. Van Loan, Johns Hopkins University Press, Baltimore, 1996.

[54]

A. Griewank, Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation, Optimization Methods & Software, 1 (1992) 35-54.

[55]

D. Y. Grigoriev, Y. N. Lakshman, pp. 96, 103

[56]

J. Håstad, B. Just, J.C. Lagarias, C.P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput., 18 (1989) 859-881.

Digital Library

[57]

M. Hitz, E, eds, Kaltofen, Second International Symposium on Parallel Symbolic Computing PASCO ¿97, 1997, ACM Press, New York

[58]

M. A. Hitz, E. Kaltofen, pp. 236, 243

[59]

M. A. Hitz, E. Kaltofen, Y. N. Lakshman, pp. 205, 212

[60]

P. Husbands, C. L. Jr. Isbell, A. Edelman

[61]

P. Iglio, G. Attardi, pp. 62, 60

[62]

P. Ion, R. Miner

[63]

D. J. Jeffrey, Proceedings of 1993 International Symposium on Symbolic Algebraic Computation, ISSAC ¿93, Bronstein, M. 1993, ACM Press, New York, 34, 41

[64]

D.J. Jeffrey, The importance of being continuous, Math. Mag., 67 (1994) 294-300.

[65]

D.J. Jeffrey, Rectifying transformations for the integration of rational trigonometric functions, J. Symb. Comput., 24 (1997) 563-573.

Digital Library

[66]

D.J. Jeffrey, A.D. Rich, The evaluation of trigonometric integrals avoiding spurious discontinuities, ACM Trans. Math. Softw., 20 (1994) 124-135.

Digital Library

[67]

R.D. Jenks, R.S. Sutor, Springer Verlag, New York, 1992.

[68]

W. Kahan, Numerical linear algebra, Can. Math. Bull., 9 (1966) 757-801.

[69]

B.S.Jr., ed. Kaliski, Springer, Berlin, 1997.

[70]

E. Kaltofen, Polynomial factorization 1987-1991, in: Proceedings of LATIN -92, Springer Verlag, Heidelberg, Germany, 1992, pp. 294-313.

[71]

E. Kaltofen, Effective Noether irreducibility forms and applications, J. Comput. Syst. Sci., 50 (1995) 274-295.

Digital Library

[72]

E. Kaltofen, Y. Lakshman, Improved sparse multivariate polynomial interpolation algorithms, in: Symbolic Algebraic Computation on International Symposium on ISSAC ¿88 Proceedings, Springer Verlag, Heidelberg, Germany, 1988, pp. 467-474.

Digital Library

[73]

E. Kaltofen, M. Monagan, pp. 59, 66

[74]

E. Kaltofen, V. Shoup, pp. 184, 188

[75]

E. Kaltofen, V. Shoup, Subquadratic-time factoring of polynomials over finite fields, Math. Comput., 67 (1998) 1179-1197.

Digital Library

[76]

E. Kaltofen, B. Trager, Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators, J. Symb. Comput., 9 (1990) 301-320.

Digital Library

[77]

M. Kaminski, D.G. Kirkpatrick, N.H. Bshouty, Addition requirements for matrix and transposed matrix products, J. Algorithms, 9 (1988) 354-364.

Digital Library

[78]

N. Karmarkar, Y. N. Lakshman, pp. 35, 42

[79]

D.E. Knuth, Addison Wesley, Reading, MA, USA, 1997.

[80]

W, ed. Küchlin, ISSAC 97, Proceedings of the 1997 International Symposium on Symbolic Algebraic Computation, 1997, ACM Press, New York

[81]

Y. N, ed. Lakshman, ISSAC 95 Proceedings of the 1996 International Symposium on Symbolic Algebraic Computation, 1996, ACM Press, New York

[82]

Y. N. Lakshman, B. Char, J. Johnson, pp. 46, 53

[83]

R. Lambert, 1996

[84]

D.F. Lawden, Springer Verlag, 1989.

[85]

D. Lazard, Résolution des systèmes d¿équation algébriques, Theor. Comput. Sci., 15 (1981) 77-110.

[86]

H. Le, C. Howlett, pp. 299, 306

[87]

A.K. Lenstra, Factoring multivariate polynomials over algebraic number fields, SIAM J. Comput., 16 (1987) 591-598.

Digital Library

[88]

A.K. Lenstra, H.W.Jr. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982) 515-534.

[89]

A. H. M, ed. Levelt, Proceedings of the 1995 International Symposium on Symbolic Algebraic Computation, ISSAC ¿95, 1995, ACM Press, New York

Digital Library

[90]

R. Loos, Computing in algebraic extensions, in: Computer Algebra, Springer Verlag, Vienna, 1982, pp. 173-187.

[91]

R.G.K. Loos, Toward a formal implementation of computer algebra, SIGSAM Bull., 8 (1974) 9-16.

Digital Library

[92]

F.S. Macaulay, Cambridge University, England, 1916.

[93]

J.L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory IT-15 (1969) 122-127.

[94]

R.J. Minnichelli, J.J. Anagnost, C.A. Desoer, An elementary proof of Kharitonov¿s stability theorem with extensions, IEEE Trans. Autom. Control, 34 (1989) 995-998.

[95]

M. B. Monagan, Proceedings of DISCO ¿93, Miola, A. 1993, Springer Verlag, Heidelberg, Germany, 81, 94

[96]

T. Mulders, A. Storjohann, pp. 181, 188

[97]

D.R. Musser, Multivariate polynomial factorization, J. ACM, 22 (1975) 291-308.

Digital Library

[98]

D.R. Musser, A. Saini, Addison-Wesley Publ. Comp, Reading, MA, 1996.

[99]

A. Norman, J. Fitch, Proceedings of DISCO ¿96, Calmet, J.Limongelli, C. 1996, Springer Verlag, Heidelberg, Germany, 271, 276

[100]

A. Odlyzko, Austria

[101]

M. Petkov¿ek, H. S. Wilf, D. Zeilberger, A, B

[102]

S. Poljak, J. Rohn, Checking robust nonsingularity is NP-hard, Math. Control Signals Syst., 6 (1993) 1-9.

[103]

R.H. Risch, The problem of integration in finite terms, Trans. Am. Math. Soc., 139 (1969) 167-189.

[104]

A. Schönhage, Quasi-GCD computations, J. Complexity, 1 (1985) 118-137.

[105]

K. Shirayanagi, Floating point Gröbner bases, Math. Comput. Simul., 42 (1996) 509-528.

Digital Library

[106]

V. Shoup, Fast construction of irreducible polynomials over finite fields, J. Symb. Comput., 17 (1994) 371-391.

Digital Library

[107]

V. Shoup, A new polynomial factorization algorithm and its implementation, J. Symb. Comput., 20 (1995) 363-397.

Digital Library

[108]

V. Shoup

[109]

V. Shoup, pp. 53, 58

[110]

H. J. Stetter, pp. 117, 124

[111]

D.R. Stoutemyer, Crimes and misdemeanors in the computer algebra trade, Notices AMS, 38 (1991) 778-785.

[112]

J. Teitelbaum, Euclid¿s algorithm and the Lanczos method over finite fields, Math. Comput., 67 (1998) 1665-1678.

[113]

B. M. Trager, Proceedings of the 1976 ACM Symposium on Symbolic Algebraic Computation, 1976, ACM, New York, 219, 228

[114]

G. Villard, pp. 32, 39

[115]

G. Villard

[116]

P. S. Wang, pp. 291, 298

[117]

S. M. Watt, P. A. Broadbery, S. S. Dooley, P. Iglio, S. C. Morrison, J. M. Steinbach, R. S. Sutor, ISSAC ¿94, Proceedings of the International Symposium on Symbolic Algebraic Computation, 1994, ACM Press, New York, 25, 31

[118]

P.J. Weinberger, L.P. Rothschild, Factoring polynomials over algebraic number fields, ACM Trans. Math. Softw., 2 (1976) 335-350.

Digital Library

[119]

D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory IT-32 (1986) 54-62.

Digital Library

[120]

L. Zhi, W. Wu, Nearest singular polynomial, J. Symb. Comput., 26 (1998) 667-675.

Digital Library

Cited By

Villard G(2025)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367127:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jsc.2024.102367
Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Show More Cited By

Index Terms

Challenges of Symbolic Computation
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Computer algebra systems
    2. Symbolic and algebraic algorithms

Recommendations

Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics
Hybrid symbolic-numeric computation
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

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 ...
Veritesting Challenges in Symbolic Execution of Java

Scaling symbolic execution to industrial-sized programs is an important open research problem. Veritesting is a promising technique that improves scalability by combining the advantages of static symbolic execution with those of dynamic symbolic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Symbolic Computation

Journal of Symbolic Computation Volume 29, Issue 6

June 2000

139 pages

ISSN:0747-7171

Editor:
Hoon Hong
North Carolina State Univ., Raleigh

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Villard G(2025)Bivariate polynomial reduction and elimination ideal over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2024.102367127:COnline publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1016/j.jsc.2024.102367
Kaltofen E(2024)Encounters in Symbolic Computation: Ideas for the AgesProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3672619(1-7)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3672619
Neiger VSalvy BSchost ÉVillard G(2024)Faster Modular CompositionJournal of the ACM10.1145/363834971:2(1-79)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3638349
Villard G(2023)Elimination ideal and bivariate resultant over finite fieldsProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597100(526-534)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597100
Karpman PPernet CSignargout HVillard GChyzak FLabahn G(2021)Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like MatricesProceedings of the 2021 International Symposium on Symbolic and Algebraic Computation10.1145/3452143.3465542(249-256)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3452143.3465542
Giorgi PGrenet BRoche DDavenport JWang DKauers MBradford R(2019)Generic Reductions for In-place Polynomial MultiplicationProceedings of the 2019 International Symposium on Symbolic and Algebraic Computation10.1145/3326229.3326249(187-194)Online publication date: 8-Jul-2019
https://dl.acm.org/doi/10.1145/3326229.3326249
Hyun SMelczer SSt-Pierre C(2019)A fast algorithm for solving linearly recurrent sequencesACM Communications in Computer Algebra10.1145/3313880.331389452:3(100-103)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3313880.3313894
Villard GKauers MOvchinnikov ASchost É(2018)On Computing the Resultant of Generic Bivariate PolynomialsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209020(391-398)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209020
Grasegger GVo NYap CEl Din M(2017)An Algebraic-Geometric Method for Computing Zolotarev PolynomialsProceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3087604.3087613(173-180)Online publication date: 23-Jul-2017
https://dl.acm.org/doi/10.1145/3087604.3087613
Zeng ZLi T(2014)NAClabACM Communications in Computer Algebra10.1145/2576802.257682947:3/4(170-173)Online publication date: 28-Jan-2014
https://dl.acm.org/doi/10.1145/2576802.2576829
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents