An elementary algorithm for computing the determinant of pentadiagonal Toeplitz matrices

Cinkir Z.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, vol.236, no.9, pp.2298-2305, 2012 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 236 Issue: 9
  • Publication Date: 2012
  • Doi Number: 10.1016/j.cam.2011.11.017
  • Journal Name: JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.2298-2305
  • Abdullah Gül University Affiliated: No

Abstract

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.