An elementary algorithm for computing the determinant of pentadiagonal Toeplitz matrices


Cinkir Z.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, cilt.236, ss.2298-2305, 2012 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 236 Konu: 9
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1016/j.cam.2011.11.017
  • Dergi Adı: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
  • Sayfa Sayıları: ss.2298-2305

Özet

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. (C) 2011 Elsevier B.V. All rights reserved.