Abstract
For sparse matrices up to size \(8\times 8\), we determine optimal choices for pivot selection in Gaussian elimination. It turns out that they are slightly better than the pivots chosen by a popular pivot selection strategy, so there is some room for improvement. We then create a pivot selection strategy using machine learning and find that it indeed leads to a small improvement compared to the classical strategy.
M.K. was supported by the Austrian FWF grants F50-04, W1214-13, and P31571.
J.M. was supported by the Land Oberüsterreich through the LIT-AI Lab.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brualdi, R.A., et al.: Combinatorial Matrix Theory. Springer, New York (1991). https://doi.org/10.1007/978-3-319-70953-6
Corless, R.M., Thornton, S.E.: The bohemian eigenvalue project. ACM Commun. Comput. Algebra 50(4), 158–160 (2017). https://doi.org/10.1145/3055282.3055289
Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Clarendon Press, Oxford (1986)
England, M.: Machine learning for mathematical software. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) ICMS 2018. LNCS, vol. 10931, pp. 165–174. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96418-8_20
Faugère, J.C.: A new efficient algorithm for computing Gröbner bases. J. Pure Appl. Algebra 139(1–3), 61–88 (1999)
Geddes, K.O., Czapor, S.R., Labahn, G.: Algorithms for Computer Algebra. Kluwer, Dordrecht (1992)
Harary, F., Palmer, E.M.: Graphical Enumeration. Academic Press, New York (1973)
Huang, Z., England, M., Wilson, D., Davenport, J.H., Paulson, L.C., Bridge, J.: Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. In: Watt, S.M., Davenport, J.H., Sexton, A.P., Sojka, P., Urban, J. (eds.) CICM 2014. LNCS (LNAI), vol. 8543, pp. 92–107. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08434-3_8
Koutschan, C.: Creative telescoping for holonomic functions. In: Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions. Texts and Monographs in Symbolic Computation, pp. 171–194. Springer (2013). https://doi.org/10.1007/978-3-7091-1616-6_7
Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manage. Sci. 3(3), 255–269 (1957). http://www.jstor.org/stable/2627454
McKay, B.D., Piperno, A.: Practical graph isomorphism, ii. J. Symbolic Comput. 60, 94–112 (2014). https://doi.org/10.1016/j.jsc.2013.09.003
Mnih, V., et al.: Human-level control through deep reinforcement learning. Nature 518(7540), 529–533 (2015)
Peifer, D., Stillman, M., Halpern-Leistner, D.: Learning selection strategies in buchberger’s algorithm (2020). arXiv preprint arXiv:2005.01917
Sloane, N.J.A.: The on-line encyclopedia of integer sequences (2020). https://oeis.org/
Sutton, R.S., Barto, A.G.: Reinforcement Learning: An Introduction. MIT Press, Cambridge (1998)
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discrete Methods 2(1), 77–79 (1981). https://doi.org/10.1137/0602010
Živković, M.: Classification of small (0,1) matrices. Linear Algebra Appl. 414(1), 310–346 (2006). https://doi.org/10.1016/j.laa.2005.10.010
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kauers, M., Moosbauer, J. (2020). Good Pivots for Small Sparse Matrices. In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2020. Lecture Notes in Computer Science(), vol 12291. Springer, Cham. https://doi.org/10.1007/978-3-030-60026-6_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-60026-6_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60025-9
Online ISBN: 978-3-030-60026-6
eBook Packages: Computer ScienceComputer Science (R0)