×

Automating algorithm selection: checking for matrix properties that can simplify computations. (English) Zbl 1423.68616

Summary: Initial findings in a study of the automatic selection of algorithms for matrix computations are reported. These include the presentation and analysis of algorithms for the detection and certification of matrix properties allowing the reliable use of a variety of special-purpose algorithms for sparse and structured matrix computations.

MSC:

68W30 Symbolic computation and algebraic computation
15A15 Determinants, permanents, traces, other special matrix functions
15B33 Matrices over special rings (quaternions, finite fields, etc.)

Software:

CSparse
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buhler, J. P.; Lenstra, H. W.; Pomerance, C., Factoring integers with the number field sieve, (The Development of the Number Field Sieve. The Development of the Number Field Sieve, Lecture Notes in Mathematics, vol. 1554 (1993), Springer-Verlag), 50-94 · Zbl 0806.11067
[2] Chen, L.; Eberly, W.; Kaltofen, E.; Saunders, B. D.; Turner, W. J.; Villard, G., Efficient matrix preconditioners for black box linear algebra, Linear Algebra Appl., 343-344, 119-146 (1993) · Zbl 0997.65073
[3] Davis, T. A.; Rajamanickam, S.; Sid-Lakhdar, W. M., A survey of direct methods for sparse linear systems, Acta Numer., 25, 383-516 (2016) · Zbl 1346.65011
[4] Dumas, J.-G.; Kaltofen, E., Essentially optimal interactive certificates in linear algebra, (Proceedings, 2014 International Symposium on Symbolic and Algebraic Computation. Proceedings, 2014 International Symposium on Symbolic and Algebraic Computation, ISSAC ’14 (2014), ACM Press), 146-153 · Zbl 1325.68274
[5] Dumas, J.-G.; Kaltofen, E.; Thomé, E.; Villard, G., Linear time interactive certificates for the minimal polynomial and determinant of a sparse matrix, (Proceedings, 2016 International Symposium on Symbolic and Algebraic Computation. Proceedings, 2016 International Symposium on Symbolic and Algebraic Computation, ISSAC ’16 (2016), ACM Press), 199-206 · Zbl 1365.65138
[6] Eberly, W., Selecting algorithms for black box matrices: checking for matrix properties that can simplify computations, (Proceedings, 2016 International Symposium on Symbolic and Algebraic Computation. Proceedings, 2016 International Symposium on Symbolic and Algebraic Computation, ISSAC ’16 (2016), ACM Press), 207-214 · Zbl 1365.65125
[7] Freivalds, R., Fast probabilistic algorithms, (Mathematical Foundations of Computer Science 1979. Mathematical Foundations of Computer Science 1979, Lecture Notes in Computer Science., vol. 74 (1979), Springer-Verlag), 57-69
[8] George, J. A., Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal., 10, 345-363 (1973) · Zbl 0259.65087
[9] Golub, G. H.; Van Loan, C. F., Matrix Computations (2012), Johns Hopkins University Press
[10] Kailath, T.; Kung, S.-Y.; Morf, M., Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., 68, 395-407 (1979) · Zbl 0433.15001
[11] Kaltofen, E.; Li, B.; Yang, Z.; Zhi, L., Exact certificates in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symb. Comput., 47, 1-15 (2012) · Zbl 1229.90115
[12] Kaltofen, E.; Nehring, M.; Saunders, B. D., Quadratic-time certificates in linear algebra, (Proceedings, 2011 International Symposium on Symbolic and Algebraic Computation. Proceedings, 2011 International Symposium on Symbolic and Algebraic Computation, ISSAC ’11 (2011), ACM Press), 171-176 · Zbl 1323.68607
[13] Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Natl. Bur. Stand., 49, 33-53 (1952)
[14] Lipton, R. J.; Rose, D. J.; Tarjan, R. E., Generalized nested dissection, SIAM J. Numer. Anal., 16, 346-358 (1979) · Zbl 0435.65021
[15] Pan, V. Y., Structured Matrices and Polynomials: Unified Superfast Algorithms (2001), Birkhäuser · Zbl 0996.65028
[16] Sherman, J.; Morrison, W. J., Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix, Ann. Math. Stat., 20, 124 (1949)
[17] Storjohann, A.; Yang, S., Linear independence oracles and applications to rectangular and low rank systems, (Proceedings, 2014 International Symposium on Symbolic and Algebraic Computation. Proceedings, 2014 International Symposium on Symbolic and Algebraic Computation, ISSAC ’14 (2014)), 381-388 · Zbl 1325.68300
[18] Villard, G., Computing the Frobenius normal form of a sparse matrix, (Computer Algebra in Scientific Computing. Computer Algebra in Scientific Computing, CACS 2000 (2000), Springer), 395-407 · Zbl 0976.65042
[19] Wiedemann, D. H., Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory, 32, 54-62 (1986) · Zbl 0607.65015
[20] Woodbury, M., Inverting Modified Matrices (1950), Statistical Research Group, Princeton University: Statistical Research Group, Princeton University Princeton, NJ, Memorandum Report 42
[21] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 1, 77-79 (1981) · Zbl 0496.68033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.