𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient algorithms for deciding the type of growth of products of integer matrices

✍ Scribed by Raphaël M. Jungers; Vladimir Protasov; Vincent D. Blondel

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
257 KB
Volume
428
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

✦ Synopsis

For a given finite set of matrices with nonnegative integer entries we study the growth with t of

We show how to determine in polynomial time whether this growth is bounded, polynomial, or exponential, and we characterize all possible behaviors.

📜 SIMILAR VOLUMES

Analysis of Algorithms for Orthogonalizi
Analysis of Algorithms for Orthogonalizing Products of Unitary Matrices
✍ Roy Mathias 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 995 KB

We consider the problem of computing u k = Qk uk-1 (where U0 is given) in finite precision (CM = machine precision) where U0 and the Qi are known to be unitary. The problem is that fik, the computed product may not be unitary, so one applies an O(n2) orthogonalizing step after each multiplication to

A p-adic algorithm for computing the inv
A p-adic algorithm for computing the inverse of integer matrices
✍ H. Haramoto; M. Matsumoto 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 270 KB

A method for computing the inverse of an (n × n) integer matrix A using p-adic approximation is given. The method is similar to Dixon's algorithm, but ours has a quadratic convergence rate. The complexity of this algorithm (without using FFT or fast matrix multiplication) is O(n 4 (log n) 2 ), the s