Abstract
Given a square matrix \(M = (u_{ij})_{n \times n}\) and an m-order matrix polynomial \(f_m(M) = \sum _{k=0}^{m} a_k M^k = a_0 I + a_1M + a_2 M^2 + \cdots + a_m M^m\), if M is a dense matrix and is perturbed to become \(M'\) at a single entry, say \(u_{pq}\), a straightforward re-calculation of \(f_{m}(M')\) would require \(O(n^{\omega } \cdot \alpha (m))\) arithmetic operations, where \(\omega < 2.3728639\) and \(\alpha (m)\) depends on the strategy of computing \(M'^k, 1 \le k \le m\) appearing in \(f_m(M')\), using the fastest square matrix multiplication algorithm by François Le Gall (ISSAC’14). In this paper, we assume that M is a dense matrix and that \(f_{m}(M)\) is known while no other additional information is available. From the perspective of the naive (a.k.a., standard row-by-column) matrix multiplication, we discuss the update of matrix polynomials. First, we present O(n)-, \(O(n^2)\)- and \(O(n^2)\)-operations update algorithms for 2-order, 3-order and 4-order matrix polynomials, respectively. Furthermore, we discuss the update of high-order matrix polynomials with a sparse coefficient vector and as a result, propose a combinatorial heuristic updating method based on directed Steiner tree in a directed acyclic graph.
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., Cvetković, D.: A Combinatorial Approach to Matrix Theory and Its Applications. CRC Press, Boca Raton (2009)
Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251–280 (1990)
Frandsen, G.S.: Dynamic matrix algorithms, manuscript, BRICS, University of Aarhus, Denmark, 11 April 2011
Frandsen, G.S., Frandsen, P.F.: Dynamic matrix rank. Theor. Comput. Sci. 410, 4085–4093 (2009)
Frandsen, G.S., Hansen, J.P., Miltersen, P.B.: Lower bounds for dynamic algebraic problems. Inf. Comput. 171, 333–349 (2001)
Frandsen, G.S., Sankowski, P.: Dynamic normal forms and dynamic characteristic polynomial. Theor. Comput. Sci. 412, 1470–1483 (2011)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore and London (1996)
Goodrich, M.T., Tamassia, R.: Algorithm Design, Foundations, Analysis, and Internet Examples. Wiley, Hoboken (2001)
Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2012)
Le Gall, F.: Faster algorithms for rectangular matrix multiplication. In: Proceedings of 53rd FOCS, pp. 514–523 (2012)
Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of 39th ISSAC, pp. 296–303 (2014)
Reif, J.H., Tate, S.R.: On dynamic algorithms for algebraic problems. J. Algorithms 22, 347–371 (1997)
Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of 45th FOCS, pp. 509–517 (2004)
Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of 44th STOC, pp. 887–898 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Ding, W., Qiu, K. (2019). Updating Matrix Polynomials. In: Du, DZ., Li, L., Sun, X., Zhang, J. (eds) Algorithmic Aspects in Information and Management. AAIM 2019. Lecture Notes in Computer Science(), vol 11640. Springer, Cham. https://doi.org/10.1007/978-3-030-27195-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-27195-4_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-27194-7
Online ISBN: 978-3-030-27195-4
eBook Packages: Computer ScienceComputer Science (R0)