An elementary algorithm for computing the determinant of pentadiagonal Toeplitz matrices

作者：Cinkir Zubeyir^*

来源：Journal of Computational and Applied Mathematics, 2012, 236(9): 2298-2305.

DOI：10.1016/j.cam.2011.11.017

• Pentadiagonal matrix
• Toeplitz matrix
• Determinant
• Fast algorithm

Over the last 25 years, various fast algorithms for computing the determinant of a pentadiagonal Toeplitz matrices were developed. In this paper, we give a new kind of elementary algorithm requiring 56 . [n-4/k] + 30k O(log n) operations, where k >= 4 is an integer that needs to be chosen freely at the beginning of the algorithm. For example, we can compute det(T-n) in n + O(log n) and 82 root n + O(log n) operations if we choose k as 56 and [root 28/15(n - 4)], respectively. For various applications, it will be enough to test if the determinant of a pentadiagonal Toeplitz matrix is zero or not. As in another result of this paper, we used modular arithmetic to give a fast algorithm determining when determinants of such matrices are non-zero. This second algorithm works only for Toeplitz matrices with rational entries.

• 出版日期2012-3