Updating Matrix Polynomials

摘要

Given a square matrix M = (u_(ij))_(n×n) and an m-order matrix polynomial f_m(M) = ∑~m_(k=0)a_kM~k = a_oI + a_1M + a_2M~2 +...+a_mM~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~w • α(m)) arithmetic operations, where ω < 2.3728639 and α(m) depends on the strategy of computing M~(tk) , 1 ≤ k ≤ m appearing in f_m(M'), using the fastest square matrix multiplication algorithm by Frangois Le Gall (ISSACT4). 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.