Dynamic normal forms and dynamic characteristic polynomial

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Standard

Dynamic normal forms and dynamic characteristic polynomial. / Frandsen, Gudmund Skovbjerg; Sankowski, Piotr.

I: Theoretical Computer Science, Bind 412, Nr. 16, 2011, s. 1470-1483.

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

Harvard

Frandsen, GS & Sankowski, P 2011, 'Dynamic normal forms and dynamic characteristic polynomial', Theoretical Computer Science, bind 412, nr. 16, s. 1470-1483. https://doi.org/10.1016/j.tcs.2010.11.049

APA

Frandsen, G. S., & Sankowski, P. (2011). Dynamic normal forms and dynamic characteristic polynomial. Theoretical Computer Science, 412(16), 1470-1483. https://doi.org/10.1016/j.tcs.2010.11.049

CBE

MLA

Vancouver

Author

Frandsen, Gudmund Skovbjerg ; Sankowski, Piotr. / Dynamic normal forms and dynamic characteristic polynomial. I: Theoretical Computer Science. 2011 ; Bind 412, Nr. 16. s. 1470-1483.

Bibtex

@article{76e62f8456f7490aaf81cf5efffcf13a,
title = "Dynamic normal forms and dynamic characteristic polynomial",
abstract = "We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n2logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n2klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2−b in additional O(nlog2nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n2) lower bound for rank-one updates and an Ω(n) lower bound for element updates.",
author = "Frandsen, {Gudmund Skovbjerg} and Piotr Sankowski",
year = "2011",
doi = "10.1016/j.tcs.2010.11.049",
language = "English",
volume = "412",
pages = "1470--1483",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier BV",
number = "16",

}

RIS

TY - JOUR

T1 - Dynamic normal forms and dynamic characteristic polynomial

AU - Frandsen, Gudmund Skovbjerg

AU - Sankowski, Piotr

PY - 2011

Y1 - 2011

N2 - We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n2logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n2klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2−b in additional O(nlog2nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n2) lower bound for rank-one updates and an Ω(n) lower bound for element updates.

AB - We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n2logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n2klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2−b in additional O(nlog2nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n2) lower bound for rank-one updates and an Ω(n) lower bound for element updates.

U2 - 10.1016/j.tcs.2010.11.049

DO - 10.1016/j.tcs.2010.11.049

M3 - Journal article

VL - 412

SP - 1470

EP - 1483

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 16

ER -