02187725

j

02187725 Pan, V.Y. On theoretical and practical acceleration of randomized computation of the determinant of an integer matrix. Zap. Nauchn. Semin. POMI 316, 163-187 (2004); translation in J. Math. Sci., New York 134, No. 5, 2411-2424 (2006). 2004 Nauka, Sankt-Peterburg EN integer matrix determinant Las Vegas algorithm block Hankel matrix generating matrix polynomial divide-and-conquer techniques Zbl 1012.65505 A new Las Vegas algorithm for computing the determinant of an $n\times n$ integer matrix $A$ is proposed. The development is based on an algorithm presented [{\it E. Kaltofen} and {\it G. Villard}, ``On the complexity of computing determinants". (Extended abstract). (English) Shirayanagi, Kiyoshi (ed.) et al., Computer mathematics. Proceedings of the 5th Asian symposium (ASCM 2001), Matsuyama, Japan, September 26--28, (2001). Singapore: World Scientific. Lect. Notes Ser. Comput. 9, 13--27 (2001; Zbl 1012.65505)] but proposes a more efficient approach for computing the coefficients of the minimum generating matrix polynomial used within this algorithm. This reduces the complexity from $O^*(n^{10/3} L)$ to $O^*(n^{16/5} L)$ bit operations, where $L=\log(n\max \vert a_{ij}\vert )$. Roughly speaking, this improvement is achieved by using divide-and-conquer techniques for solving linear systems having block Hankel structure. Daniel Kressner (Zagreb)