Numerical analysis of secular functions of a real symmetric positive definite Toeplitz matrix.

Kostic, Aleksandra

Abstract: In this note we present numerical analysis of secular functions of a real symmetric positive definite Toeplitz matrix (RSPDTM). In paper (Kostic et al., 2011) is given general form of secular function of RSPDTM. From numerical analysis of secular functions emerged new algorithm which represents upgrading the cheapest algorithm by 14 percent or by 17 percent, respectively, when matrices have large dimension.

Key words: eigenvalue problem, Toeplitz matrix, secular function, numerical analysis

1. INTRODUCTION

From Pisarenko's work (Pisarenko, 1973) the problem of finding the smallest eigenvalue of a real symmetric, positive definite Toeplitz matrix (RSPDTM) plays an important role in signal processing. The computation of the minimum eigenvalue of [T.sub.n] was studied in, e.g. in (Cybenko & Van Loan, 1986; Kostic, 2004; Kostic & Cohodar, 2008; Mackens & Voss, 1997, 2000; Melman, 2006; Mastronardi & Boley, 1999).

In this paper we bring criteria for comparison of different secular functions of RSPDTM and develop new method for calculating the smallest eigenvalue of the RSPDTM, which is based on using the smallest roots from two different secular functions.

The paper is organized as follows. In Section 2 we present the basic properties of Toeplitz matrices and the notation we will use. In Section 3 we present criteria for comparison, numerical analyses and new algorithm. In Section 4 we present conclusion of the paper.

2. PRELIMINARIES

The Teoplitz matrix is quadratic matrix which has the same elements in its respective diagonals, which means that [a.sub.ij] = [a.sub.n+1-j,n+1-i]. Because we take in consideration symmetric matrices it also means that [a.sub.ij] = [a.sub.ij]. The Teoplitz matrix is defined with vector (1, [t.sub.1], ..., [t.sub.n]) [member of] [R.sup.n] so the [(i,j).sup.th] element of an n x n symmetric Toeplitz matrix [T.sub.n] is given by [t.sub.[absolute value of i-j]]. We can conclude, form above given, that Teoplitz matrices are centrosymmetric and satisfy J[T.sub.n] J = [T.sub.n]. We use I for the identity matrix and J:= [([[delta].sub.i,n+1-i]).sub.i,j=1,...,n] for the exchange, or "flip" matrix.

3. NUMERICAL ANALYSES AND CRITERIA FOR COMPARISON

Kostic, Velic & Bektesevic (Kostic et al., 2011) gave general form of the secular function of RSPDTM [T.sub.n]:

[q.sub.k]([lambda]) = [p.sub.n]([lambda]/[p.sub.n-k]([lambda]) (1)

where k<n, [p.sub.n] ([lambda]) and [p.sub.n-k]([lambda]) are characteristic polynomials of RSPDTM [T.sub.n] and [T.sub.n-1] respectively.

In paper (Kostic et al., 2011) is given explained idea about pole shifting of secular function from the smallest root of the secular function. Secular functions given with (1) can be compared in several ways, e.g.: average distance between the root and the pole of secular function, modeling simplicity of secular function, or speed of the used algorithm on different secular functions.

To analyze secular functions of RSPDTM we considered the following class of Toeplitz matrices:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

where m is chosen such that the diagonal of T, is normalized to [t.sub.0] = 1. [T.sub.[theta]] = ([t.sub.i,j]) = (cos([theta](i-j))) and [[eta].sub.k] and [[theta].sub.k] are uniformly distributed random in the interval [0,1] (Cybenko & Van Loan, 1986). We considered dimensions n=32, 64, 128, 256, 512 and 1024 of RSPDTM.

In case of using first criteria, when distance between the root and the pole of secular function of RSPDTM which we will denote with letter d for different k and dimension n=32 we get following table:

Tab. 1. The distance between the smallest root and the pole

k d

1 5.032 * [10.sup.-3]
2 8.9147 * [10.sup.-3]
3 1.2703 * [10.sup.-2]
4 1.85906 * [10.sup.-2]
5 2.5839 * [10.sup.-2]
6 3.39655 * [10.sup.-2]
7 4.49125 * [10.sup.-2]
15 1.77528 * [10.sup.-1]
16 2.00584 * [10.sup.-1]
17 2.2756 * [10.sup.-1]
28 7.139 * [10.sup.-1]
29 7.85097 * [10.sup.-1]

However, even though the distance between the smallest root and the pole is very important, it is not absolutely crucial for the quality of the secular function.

Second criteria is also important because it depends of the modeling skills of given secular function. In paper (Kostic et al., 2010) we have seen one of the ways for modeling secular function for k=2.

We are sure we can use Newton's method on every secular function, because iteration

[lambda] = [lambda] - [q.sub.n-k]/[q.sub.n-k] (3)

can easily be transformed to

[lambda] = [lambda] - 1/[p.sub.n]/[p.sub.n] - [p.sub.n-k]/[p.sub.n-k] (4)

whereas respective quotients can be calculated by using Melman's theorem (Melman, A. 2006).:

Theorem 1. The Newton step for the characteristic polynomial [p.sub.n]([lambda]) of a n x n symmetric positive definite Toeplitz matrix [T.sub.n] at [lambda] = [bar.[lambda]] < [[lambda].sub.1] is given by:

N ([bar.[lambda]]) = q ([bar.[lambda]])/[[summation].sup.n.sub.j=1] (2j-n) [w.sup.2.sub.j] (5)

where q is as in Definition 1. and the first row of [T.sub.n], is given by (1,[t.sup.T]) and w = ([w.sub.1], ..., [W.sub.n-1]) = JN[([T.sub.n-1] - [[bar.[lambda]]I).sup.-1] t. For compactness of writing, we have set [w.sub.n]=1.

Table 2 contains the average number of Durbin steps, where we used Newton's method applied for different secular functions (different k), needed to determine each of the dimension n=32, 64, 128, 256, 512 and 1024 in 100 test problems.

From the table can be seen that the best results are obtained for n=32 and k=3; n=64 and k=4; n=128 and k=5; n=256 and k=6. By analogy best results are obtained for n=512 and k= 7.

If we for given n and k combine given secular functions [q.sub.n-k] and [q.sub.n-1] in case when we are in front of the smallest root of the functions we get new algorithm which is significantly better than already existing algorithms. Here we use the fact that by using Newton's method on function [q.sub.n-1] top boundary of the smallest eigenvalue is always obtained. By comparing the best algorithm for secular function without exploiting symmetry given in (Kostic, A. & Voss, H. 2002) we get

It can be seen that improvement of 14 percent is obtained for dimension n = 512 and improvement of 17 for dimension n = 1024. Now, it is clear that the biggest improvement of 17 percent is obtained for biggest matrix dimension.

4. CONCLUSION

In this paper we bring different criteria for comparison of different secular functions (different k). We made serious analysis using third criteria by applying Newton's method on different secular functions. If we combine two secular functions [q.sub.n-k] and [q.sub.n-1] and apply Newton's method on them we get new algorithm which enables us to get smallest eigenvalue of RSPDTM faster. We also used fact that by applying Newton's method on function [q.sub.n-1] top boundary of the smallest eigenvalue is always obtained.

It would be interesting to consider root finding method for rational interpolation of secular functions [q.sub.n-k] and [q.sub.n-1], which will be subject of our further research.

In further research we plan to use symmetry properties of RSPDTM, because symmetry properties should accelerate already existing algorithms.

5. REFERENCES

Cybenko, G. & Van Loan, C.F. (1986). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Stat. Comput, Vol. 7, No. 1, pp. 123-131. MRO819462 (87b:65042)

Gohberg, I.C. & Semencul, A. A. (1972). The inversion of finite Toeplitz matrices and their continual analogues. (Russian), Mat. Issued. Vol. 7., No. 2 (24), pp. 201-223. MR0353038 (50:5524)

Kostic A. (2004). Verfahren zur Bestimmung einiger extremaler Eienwerte einer symmetrischen Toeplitz Matrix, Shaker Verlag, ISBN 3-8322-3235-4, Aachen

Kostic A. & Cohodar M. (2008). Quadratic approximation of characteristic polynomial of symmetric positive definite Toeplitz matrix, Proceedings of 19th International DAAAM Symposium, ISBN 978-3-901509-68-1, ISSN 1726-9679, pp 192

Kostic, A. & Voss, H. (2002). A method of order 1 + [square root of 3] for computing the smallest eigenvalue of a symmetric Toeplitz matrix, WSEAS Transactions of Mathematics, Vol. 1, pp. 1-7

Kostic A., Velic M. & Bektesevic J. (2011). Practical strategies for stabilisation of algorithms based on secular equations of RSPDTM, Proceedings of 10th International Conference on Accomplishments in Electrical and Mechanical Engineering and Information technology (10; 2011; Banja Luka), ISBN 978-99938-39-36-1, COBISS.BH-ID 2029592

Kostic A., Velie M. & Hadziabdic V. (2010). New secular equation of RSPDT matrix and its rational approximation, Proceedings of 21th International DAAAM Symposium, ISBN 978-3-901509-73-51 ,ISSN 1726-9679, pp 0043

Mackens, W. & Voss, H. (2000). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods, SIAMJ. Sci. Comput., Vol. 21. No. 4, pp. 1650-1656 MR1756049 (2001g:65043)

Mackens, W. & Voss, H. (1997). The minimum eigenvalue of a symmetric positive definite Toeplitz matrix and rational Hermitian interpolation, SIAM J. Matr. Anal. Appl, Vol. 18. pp. 523-534

Mastronardi, N & Boley, D. (1999). Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Comput., Vol. 20, No. 5, pp. 1921-1927. MR 1694690

Melman, A. (2006). Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix, Mathematics of computation, Vol. 75, No 254, pp. 817-832, S 025-5718(05)01796-5

Pisarenko, V. F. (1973). The retrieval of harmonics from a covariance function. Geophys, J. R. astr. Soc., Vol. 33., 347-366

Tab. 2. Average number of Durbin steps, where we used
Newton's method applied for different secular functions
(different k)

 n = 32 n = 64 n = 128 n = 256

k steps k steps k steps k steps

1 8.17 1 9.83 1 10.63 1 12.15
2 5.97 2 6.82 2 8.09 2 9.31
3 5.77 3 5.94 3 6.89 3 8.41
4 5.96 4 5.84 4 6.52 4 7.69
5 6.32 5 6.28 5 6.26 5 7.03
6 6.64 6 6.59 6 6.32 6 6.81
15 7.88 31 8.869 63 9.07 127 10.2
16 7.92 32 8.89 64 9.09 128 10.2
17 7.96 33 8.92 65 9.09 129 10.2
28 8.33 60 9.41 120 9.33 252 10.39
29 8.36 61 9.41 121 9.33 253 10.39

Tab. 3. Comparison of the new algorithm with the best existing
algorithm (Kostic, A. & Voss, H. 2002)

dim new best

32 5.39 4.34
64 5.19 5.14
128 5.22 5.25
256 5.52 5.84
512 5.65 6.62
1024 16.05 17.26