Abstract
Parametric linear systems are linear systems of equations in which some symbolic parameters, that is, symbols that are not considered to be candidates for elimination or solution in the course of analyzing the problem, appear in the coefficients of the system. In this work we assume that the symbolic parameters appear polynomially in the coefficients and that the only variables to be solved for are those of the linear system. The consistency of the system and expression of the solutions may vary depending on the values of the parameters. It is well-known that it is possible to specify a covering set of regimes, each of which is a semi-algebraic condition on the parameters together with a solution description valid under that condition.
We provide a method of solution that requires time polynomial in the matrix dimension and the degrees of the polynomials when there are up to three parameters. In previous methods the number of regimes needed is exponential in the system dimension and polynomial degree of the parameters. Our approach exploits the Hermite and Smith normal forms that may be computed when the system coefficient domain is mapped to the univariate polynomial domain over suitably constructed fields. Our approach effectively identifies intrinsic singularities and ramification points where the algebraic and geometric structure of the matrix changes. Parametric eigenvalue problems can be addressed as well: simply treat \(\lambda \) as a parameter in addition to those in \(\mathbf {A}\) and solve the parametric system \((\lambda \mathbf {I} - \mathbf {A})\mathbf {u} = 0\). The algebraic conditions on \(\lambda \) required for a nontrivial nullspace define the eigenvalues. We do not directly address the problem of computing the Jordan form, but our approach allows the construction of the algebraic and geometric eigenvalue multiplicities revealed by the Frobenius form, which is a key step in the construction of the Jordan form of a matrix.
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
Notes
- 1.
This is merely an anecdote, but one of the present authors attests that this really has happened.
References
Boyer, B., Kaltofen, E.L.: Numerical linear system solving with parametric entries by error correction. In: Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. pp. 33–38 (2014)
Buchberger, B.: Applications of Gröbner bases in non-linear computational geometry. In: Janßen, R. (ed.) Trends in Computer Algebra, pp. 52–80. Springer, Berlin, Heidelberg (1988)
Camargos Couto, A.C., Moreno Maza, M., Linder, D., Jeffrey, D.J., Corless, R.M.: Comprehensive LU factors of polynomial matrices. In: Slamanig, D., Tsigaridas, E., Zafeirakopoulos, Z. (eds.) Mathematical Aspects of Computer and Information Sciences, pp. 80–88. Springer International Publishing, Cham (2020)
Corless, R.M., Moreno Maza, M., Thornton, S.E.: Jordan canonical form with parameters from Frobenius form with parameters. In: Blömer, J., Kotsireas, I.S., Kutsia, T., Simos, D.E. (eds.) MACIS 2017. LNCS, vol. 10693, pp. 179–194. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72453-9_13
Corless, R.M.: Essential Maple 7: An Introduction For Scientific Programmers. Springer Science & Business Media, Berlin (2002)
Corless, R.M., Jeffrey, D.J.: The Turing factorization of a rectangular matrix. SIGSAM Bull. 31(3), 20–30 (1997). https://doi.org/10.1145/271130.271135
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Science & Business Media, Berlin (2013)
Dautray, R., Lions, J.: Mathematical Analysis and Numerical Methods for Science and Technology. Springer-Verlag, Berlin (1988). https://doi.org/10.1007/978-3-642-61566-5
Dessombz, O., Thouverez, F., Laîné, J.P., Jézéquel, L.: Analysis of mechanical systems using interval computations applied to finite element methods. J. Sound Vibration 239(5), 949–968 (2001). https://doi.org/10.1006/jsvi.2000.3191
Giesbrecht, M., Kim, M.S.: Computing the Hermite form of a matrix of Ore polynomials. J. Algebra 376, 341–362 (2013)
Goldman, L.: Integrals of multinomial systems of ordinary differential equations. J. Pure Appl. Algebra 45(3), 225–240 (1987). https://doi.org/10.1016/0022-4049(87)90072-7
Higham, N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008)
Jensen, K.: Coloured Petri nets. Vol. 1. Monographs in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin (1997). https://doi.org/10.1007/978-3-642-60794-3, https://doi.org/10.1007/978-3-642-60794-3, basic concepts, analysis methods and practical use, Corrected reprint of the second (1996) edition
Kaltofen, E., Krishnamoorthy, M., Saunders, B.D.: Fast parallel computation of Hermite and Smith forms of polynomial matrices. SIAM J. Algebraic Discrete Methods 8(4), 683–690 (1987)
Kaltofen, E.L., Pernet, C., Storjohann, A., Waddell, C.: Early termination in parametric linear system solving and rational function vector recovery with error correction. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation. pp. 237–244 (2017)
Kapur, D., Sun, Y., Wang, D.: An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system. J. Symb. Comput. 49, 27–44 (2013)
Kolev, L.V.: Outer solution of linear systems whose elements are affine functions of interval parameters. Reliab. Comput. 8(6), 493–501 (2002). https://doi.org/10.1023/A:1021320711392
Lemaire, F., Maza, M.M., Xie, Y.: The regularchains library. In: Maple conference. vol. 5, pp. 355–368 (2005)
Montes, A.: The Gröbner Cover. ACM, vol. 27. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03904-2
Montes, A., Wibmer, M.: Gröbner bases for polynomial systems with parameters. J. Symb. Comput. 45(12), 1391–1425 (2010)
Muhanna, R.L., Mullen, R.L.: Uncertainty in mechanics problems–interval-based approach. J. Eng. Mech. 127(6), 557–566 (2001)
Rahman, S.A., Zou, X.: Modelling the impact of vaccination on infectious diseases dynamics. J. Biol. Dyn. 9(sup1), 307–320 (2015)
Savageau, M.A., Voit, E.O., Irvine, D.H.: Biochemical systems theory and metabolic control theory. I. Fundamental similarities and differences. Math. Biosci. 86(2), 127–145 (1987). https://doi.org/10.1016/0025-5564(87)90007-1
Savageau, M.A., Voit, E.O., Irvine, D.H.: Biochemical systems theory and metabolic control theory. II. The role of summation and connectivity relationships. Math. Biosci. 86(2), 147–169 (1987). https://doi.org/10.1016/0025-5564(87)90008-3
Sit, W.Y.: An algorithm for solving parametric linear systems. J. Symb. Comput. 13(4), 353–394 (1992)
Sloane, N.: The on-line encyclopedia of integer sequences (2020), http://oeis.org
Storjohann, A.: Algorithms for matrix canonical forms. Ph.D. thesis, ETH Zurich (2000)
Trench, W.F.: Properties of some generalizations of Kac-Murdock-Szego matrices. Contemp. Math. 281, 233–246 (2001)
Wahl, L.M., Betti, M.I., Dick, D.W., Pattenden, T., Puccini, A.J.: Evolutionary stability of the lysis-lysogeny decision: Why be virulent? Evolution 73(1), 92–98 (2019)
Weispfenning, V.: Comprehensive Gröbner bases. J. Symb. Comput. 14(1), 1–29 (1992)
Winkels, H., Meika, M.: An integration of efficiency projections into the Geoffrion approach for multiobjective linear programming. Eur. J. Oper. Res. 16(1), 113–127 (1984)
Acknowledgements
This work was supported by the Natural Sciences and Engineering Research Council of Canada and by the Ontario Research Centre for Computer Algebra. The third author, L. Rafiee Sevyeri, would like to thank the Symbolic Computation Group (SCG) at the David R. Cheriton School of Computer Science of the University of Waterloo for their support while she was a visiting researcher there.
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
Corless, R.M., Giesbrecht, M., Rafiee Sevyeri, L., Saunders, B.D. (2020). On Parametric Linear System Solving. 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_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-60026-6_11
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)