Engineering
Vol.5 No.5A(2013), Article ID:31804,4 pages DOI:10.4236/eng.2013.55A004
A New Algorithm for Computing the Determinant and the Inverse of a Pentadiagonal Toeplitz Matrix*
Department of Mathematics and Information Science, Zhangzhou Normal University, Zhangzhou, China
Email: yuehuich@fjzs.edu.cn
Copyright © 2013 Yuehui Chen. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Received January 25, 2013; revised February 26, 2013; accepted March 4, 2013
Keywords: Pentadiagonal Matrix; Toeplitz Matrix; Determinant; Nonsingular; Inverse
ABSTRACT
An effective numerical algorithm for computing the determinant of a pentadiagonal Toeplitz matrix has been proposed by Xiao-Guang Lv and others [1]. The complexity of the algorithm is (9n + 3). In this paper, a new algorithm with the cost of (4n + 6) is presented to compute the determinant of a pentadiagonal Toeplitz matrix. The inverse of a pentadiagonal Toeplitz matrix is also considered.
1. Introduction
Pentadiagonal Toeplitz matrix linear systems often occur in several fields such as numerical solution of differential equations, interpolation problems, boundary value problems [1-5], etc. In these areas, the determinants and the inversions of pentadiagonal Toeplitz matrices are considered. In recent years they have become one of the most important and active research field of applied mathematics and computational mathematics increasingly.
In [2], E. Kilic, M. Ei-Mikkawy presented a fast and reliable algorithm with the cost of for evaluating special nth-order pentadiagonal Toeplitz determinants. In [1], X.G. Lv, T.Z. Huang, J. Le presented an algorithm with the cost of for calculating the determinant of a pentadiagonal Toeplitz matrix and an algorithm for calculating the inverse of a pentadiagonal Toeplitz matrix.
In this paper, we present new algorithms for computing the determinant and the inverse of an n-by-n pentadiagonal Toeplitz matrix. The complexity of the algorithms are and respectively.
This paper is organized as follows: in Section 2, we present some useful notations and lemmas. In Section 3, we are going to derive new two algorithms. Finally, we give an numerical examples to show the performance of our algorithms in Section 4.
2. Notations and Preliminaries
Definition 2.1 Let be an matrix.
is called persymmetric if it symmetric about its northeast-southwest diagonal, i.e., for all and.
Definition 2.2 Form as
is called Toeplitz matrix.
Toeplitz matrices are all persymmetric matrices.
Lemma 2.1 [6] Let be an matrix. Then
(1) is persymmetric matrix if and only if ;
(2) If is nonsingular Toeplitz matrix, is also a Toeplitz matrix, where is the exchange matrix, i.e., , is the ith column of identity matrix of order.
Without loss of generality, we suppose in the paper. By computing simply, we have the following conclusion:
Lemma 2.2 Let be an Toeplitz matrix
(2.1)
Then the inverse of is an Toeplitz matrix, and
where
and.
Lemma 2.3 Let where and
are matrices of size
respectively. is nonsingular. Then is nonsingular if and only if is nonsingular, and
In the current paper, we consider the pentadiagonal Toeplitz matrix of the form
(2.2)
3. Main Results
Decompose the pentadiagonal Toeplitz matrix (2.2) as the following:
where
Partition M into where is matrix (2.1),
is zero matrix of size,
of size and
of size.
Thus
where
Denote
Thus
It is noticed that
We have
According to the Lemma 2.3 and deduction above, we have the following results:
Theorem 3.1 Let be the pentadiagonal Toeplitz matrix as (2.2), then (1) is nonsingular if and only if and
(2)
When , we have that is nonsingular, and
where
and
Denote and
We have
i.e.,
(3.2)
i.e.,
(3.4)
From the Lemma 2.1 and we have
Thus
Denote
(3.5)
Then
According to the deduction above, we can obtain Theorem 3.2:
Theorem 3.2 Let the pentadiagonal Toeplitz matrix as (2.2) be nonsingular. Then
where
as above.
Combining with Theorem 3.1 and Theorem 3.2, we obtain the following algorithm:
Algorithm 3.1 (Computing)
(1) Input;
(2) Compute
(3) Compute .
Algorithm 3.2 (Computing)
(1) Using (3.1), calculate;
(2) Using (3.2), calculate;
(3) Using (3.4), calculate;
(4) Using (3.3) and (3.5), calculate;
(5) Calculate;
(6) Calculate.
Let us now have a look at the number of multiplications and divisions executed by Algorithm 3.1 and 3.2. For Algorithm 3.1, in Step 2, it takes about operations. Step 3 amounts to 2 operations. On the whole, we need about operations to compute. Algorithm 3.1 is better than E. Killic’s algorithm [2] with the cost of and X.G. Lv’s algorithm [1] with the cost of. For Algorithm 3.2, in Step 1, it takes 4 operations. Step 2 amounts to operations. Step 3 amounts to operations. The cost of step 4 is about, we make use of the persymmetric matrix. Therefore, we need about operations computing. Our algorithm is better than X.G. Lv’s algorithm [1] with the cost of.
4. An Example
Consider the pentadiagonal Toeplitz matrix as
By Algorithm 3.1, we have
So
Using Algorithm 3.2, we obtain
So
REFERENCES
- X. G. Lv, T. Z. Huang and J. Le, “A Note on Computing the Inverse and the Determinant of a Pentadiagonal Toeplitz Matrix,” Applied Mathematics and Computation, Vol. 206, No. 1, 2008, pp. 327-331. doi:10.1016/j.amc.2008.09.006
- E. Kilic and M. Ei-Mikkawy, “A Computational Algorithm for Special nth Order Pentadiagonal Toeplitz Determinants,” Applied Mathematics and Computation, Vol. 199, No. 2, 2008, pp. 820-822. doi:10.1016/j.amc.2007.10.022
- J. M. McNally, “A Fast Algorithm for Solving Diagonally Dominant Symmetric Pentadiagonal Toeplitz Systems,” Journal of Computational and Applied Mathematics, Vol. 234, No. 4, 2010, pp. 995-1005. doi:10.1016/j.cam.2009.03.001
- S. S. Nemani, “A Fast Algorithm for Solving Toeplitz Penta-Diagonal Systems,” Applied Mathematics and Computation, Vol. 215, No. 11, 2010, pp. 3830-3838.
- Y. H. Chen and C. Y. Yu, “A New Algorithm for Computing the Inverse and the Determinant of a Hessenbert Matrix,” Applied Mathematics and Computation, Vol. 218, 2011, pp. 4433-4436. doi:10.1016/j.amc.2011.10.022
- G. H. Golub and C. F. Van Loan, “Matrix Computations,” 3rd Edition, Johns Hopkings University Press, Baltimore and London, 1996, pp. 193-202.
NOTES
*Project supported by the Natural Science Foundation of Fujian Province, China (2012D139).