Research article

A smoothing spline algorithm to interpolate and predict the eigenvalues of matrices extracted from the sequence of preconditioned banded symmetric Toeplitz matrices

  • Received: 31 January 2024 Revised: 12 April 2024 Accepted: 15 April 2024 Published: 30 April 2024
  • MSC : 65F15, 34L16, 34L20, 35P20, 35P15, 47A75

  • Understanding the eigenvalue distribution of sequence Toeplitz matrices has advanced significantly in recent years. Notable contributors include Bogoya, Grudsky, Böttcher, and Maximenko, who have derived precise asymptotic expansions for these eigenvalues under certain conditions related to the generating function as the matrix size increases. Building on this foundation, the Stefano Serra-Capizzano conjectured that, under certain assumptions about Ω and Φ, a similar expansion may hold for the eigenvalues of a sequence of preconditioned Toeplitz matrices T1n(Φ)Tn(Ω), given a monotonic ratio r=Ω/Φ. In contrast to current eigenvalue solvers, this work presents a novel method for efficiently calculating the eigenvalues of a sequence of large preconditioned banded symmetric Toeplitz matrices (PBST). Our algorithm uses a higher-order spline fitting extrapolation technique to gather spectral data from a smaller sequence of PBST matrices in order to forecast the spectrum of bigger matrices.

    Citation: Salima Kouser, Shafiq Ur Rehman, Mabkhoot Alsaiari, Fayyaz Ahmad, Mohammed Jalalah, Farid A. Harraz, Muhammad Akram. A smoothing spline algorithm to interpolate and predict the eigenvalues of matrices extracted from the sequence of preconditioned banded symmetric Toeplitz matrices[J]. AIMS Mathematics, 2024, 9(6): 15782-15795. doi: 10.3934/math.2024762

    Related Papers:

    [1] Xiaofeng Guo, Jianyu Pan . Approximate inverse preconditioners for linear systems arising from spatial balanced fractional diffusion equations. AIMS Mathematics, 2023, 8(7): 17284-17306. doi: 10.3934/math.2023884
    [2] Jiaqi Qu, Yunlan Wei, Yanpeng Zheng, Zhaolin Jiang . Fast algorithms for a linear system with infinitesimal generator structure of a Markovian queueing model. AIMS Mathematics, 2025, 10(3): 6546-6559. doi: 10.3934/math.2025299
    [3] Chih-Hung Chang, Ya-Chu Yang, Ferhat Şah . Reversibility of linear cellular automata with intermediate boundary condition. AIMS Mathematics, 2024, 9(3): 7645-7661. doi: 10.3934/math.2024371
    [4] Yuwen He, Jun Li, Lingsheng Meng . Three effective preconditioners for double saddle point problem. AIMS Mathematics, 2021, 6(7): 6933-6947. doi: 10.3934/math.2021406
    [5] Na Li, Qin Zhong . Smoothing algorithm for the maximal eigenvalue of non-defective positive matrices. AIMS Mathematics, 2024, 9(3): 5925-5936. doi: 10.3934/math.2024289
    [6] Shahbaz Ahmad, Adel M. Al-Mahdi, Rashad Ahmed . Two new preconditioners for mean curvature-based image deblurring problem. AIMS Mathematics, 2021, 6(12): 13824-13844. doi: 10.3934/math.2021802
    [7] Yanpeng Zheng, Xiaoyu Jiang . Quasi-cyclic displacement and inversion decomposition of a quasi-Toeplitz matrix. AIMS Mathematics, 2022, 7(7): 11647-11662. doi: 10.3934/math.2022649
    [8] Xueyong Wang, Gang Wang, Ping Yang . Novel Pareto $ Z $-eigenvalue inclusion intervals for tensor eigenvalue complementarity problems and its applications. AIMS Mathematics, 2024, 9(11): 30214-30229. doi: 10.3934/math.20241459
    [9] João Lita da Silva . Spectral properties for a type of heptadiagonal symmetric matrices. AIMS Mathematics, 2023, 8(12): 29995-30022. doi: 10.3934/math.20231534
    [10] Pablo Díaz, Esmeralda Mainar, Beatriz Rubio . Total positivity, Gramian matrices, and Schur polynomials. AIMS Mathematics, 2025, 10(2): 2375-2391. doi: 10.3934/math.2025110
  • Understanding the eigenvalue distribution of sequence Toeplitz matrices has advanced significantly in recent years. Notable contributors include Bogoya, Grudsky, Böttcher, and Maximenko, who have derived precise asymptotic expansions for these eigenvalues under certain conditions related to the generating function as the matrix size increases. Building on this foundation, the Stefano Serra-Capizzano conjectured that, under certain assumptions about Ω and Φ, a similar expansion may hold for the eigenvalues of a sequence of preconditioned Toeplitz matrices T1n(Φ)Tn(Ω), given a monotonic ratio r=Ω/Φ. In contrast to current eigenvalue solvers, this work presents a novel method for efficiently calculating the eigenvalues of a sequence of large preconditioned banded symmetric Toeplitz matrices (PBST). Our algorithm uses a higher-order spline fitting extrapolation technique to gather spectral data from a smaller sequence of PBST matrices in order to forecast the spectrum of bigger matrices.



    In mathematics, linear algebra is essential for resolving real-world issues. Any numerical approach used to approximated differential equations leads to different matrices, and among them are structured, multilevel, banded matrices, and matrix-sequences play an important role. At the beginning of the 20th century, Otto Toeplitz (1881–1940), a German mathematician, introduced the notion of the Toeplitz matrix and the Toeplitz operator. After the Fourier transformation was discovered, in order to determine the spectral theory of the Toeplitz matrix associated with the Laurent operators L=(Φji)i,jZ on the Lebesgue space ł2(z), Otto Toeplitz employed the multiplication operation. This resulted in the following:

    Ψ(p)=jZΦjeijp.

    Stated otherwise, this defines the Toeplitz matrix of size n with a fixed entry along each diagonal as

    Tn(Φ)=[Φ0Φ1Φ2Φ(n1)Φ1Φ0Φ1Φ1Φ2Φ1Φ2Φ1Φ0Φ1Φn1Φ2Φ1Φ0]. (1.1)

    Grenander and Szego [4] state that the nth Toeplitz matrix generated by Φ, for a complex valued Lebesgue integrable function Φ:[π,π]C, is given by

    Tn(Φ)=[ˆΦij]ni,j=1,

    where the Fourier coefficients of Φ are denoted by the quantities ˆΦk, i.e.,

    ˆΦk=12πππΦ(Θ)eikΘdΘ,kZ.

    The Toeplitz sequence created by Φ, also known as the generating function of {Tn(Φ)}n, is denoted as {Tn(Φ)}n. The spectral properties of all the matrices Tn(Φ) where Φ is real-valued are well-known, ranging from the eigenvalue localization to the Weyl sense asymptotic spectral distribution. Specifically, if Φ is real-valued, Φ represents {Tn(Φ)} spectrally; see, for example, [18] and the references therein for further details.

    More specifically, any eigenvalue of Tn(Φ) with Φ being real-valued and not identically constant falls in (mΦ,MΦ), where mΦ and MΦ represent the infimum and supremum of Φ, respectively. In the event that Φ is constant, there is no problem; if Φ=m then Tn(Φ)=mIn, where In represents the identity of size n. Therefore, Tn(Φ) is Hermitian positive definite if MΦ>0 and Φ is non-negative almost everywhere. The eigenvalues of banded symmetric Toeplitz (BST) matrices asymptotically expand when the generating symbol is a real-valued cosine trigonometry polynomial (RCTP) in the form specified by Ekstrm et al. [7]

    Ω(Θ)=ˆΩ0+2mj=1ˆΩjcos(jΘ),ˆΩ0,ˆΩ1,,ˆΩmR,mN. (1.2)

    Over the interval [0,π], the RCTP is either monotonically increasing or decreasing. The n×n real banded symmetric Toeplitz (BST) matrix is generated by Ω. We focus on the following assumptions in this paper: Tn(Ω), Tn(Φ) are both real symmetric Toeplitz matrices, given

    Ω(Θ)=ˆΩ0+2m1j=1ˆΩjcos(jΘ),ˆΩ0,ˆΩ1,,ˆΩm1R,m1N.Φ(Θ)=ˆΦ0+2m2j=1ˆΦjcos(jΘ),ˆΦ0,ˆΦ1,,ˆΦm2R,m2N.

    Tn(Φ) is a positive definite matrix.

    ● We take Pn(Ω,Φ)=T1n(Ω)Tn(Φ) as the 'preconditioned' matrix and define r=Φ/Ω.

    The Toeplitz matrix of order n×n with bandwidth 2m+1 was generated by the symbol p{Ω,Φ}, where m{m1,m2} (notice that m=m1 when p=Ω and m=m2 when p=Φ). Consequently, the matrix is

    The quick solution of large Toeplitz linear systems requires matrices of the form Pn(Ω,Φ) (in relation to the preconditioned conjugate gradient method). Their spectral characteristics have been thoroughly investigated. To be more precise, if r=m, then Pn(Ω,Φ)=rIn; on the other hand, all eigenvalues of Pn(Ω,Φ) belong to (mr,Mr) if mr<Mr (see, for example, [21]) and r=Φ/Ω is the Weyl sense spectral distribution for the complete sequence {Pn(Ω,Φ)}n [24]. If a function increases or decreases over the interval [0,π], it is considered monotone in our context. Assuming that r=Φ/Ω is monotone, we experimentally demonstrate in this article that the following asymptotic expansion holds [5] for every n, every integer α0, and every k=1,,n.

    υk(Pn(Ω,Φ)=r(Θk,n)+αk=1ζj(Θk,n)Λj+ϵk,n,α, (1.3)

    where

    ● eigenvalues of Pn(Ω,Φ) are arranged in either non-increasing or non-decreasing order, contingent on whether r is increasing or decreasing;

    ● a series of functions from [0,π] to R that depends entirely on r is denoted as {ζj}j=1,2,;

    Λ=1n+1 and Θk,n=kπn+1=kπΛ;

    ● the remainder (error) is ϵj,n,α=O(Λα+1). This results in an inequality for some constant Cα that depends only on α and r: |ϵk,n,α|CαΛα+1.

    If the RCTP Φ is monotone and satisfies other conditions, like Φ(Θ)0 and Φ(Θ)0 for Θ{0,π}, the result is proven in [14,16,17]. This is the pure Toeplitz case, meaning that Pn(Ω,Φ)=Tn(Φ) and r=Φ are equivalent for Ω=1. Particularly interesting are

    Ωq(Θ)=(22cosΘ)q,q=1,2, (1.4)

    that appear when discretizing differential equations. Sadly, if q2, the condition that Φ(0)0 is not satisfied. Even in this "degenerate case" the higher order approximation (1.3) holds, according to numerical evidence in [22]. Here, given the preconditioned matrices Pn(Ω,Φ), we numerically prove the same. Theoretically, the demonstration of the aforementioned conjecture when α=0 complements the numerical testing.

    The authors of [22] utilized the asymptotic expansion (1.3) to approximate υk(Tn(Ω)) for very large n, given that the values for fairly sized n1,,ns with Θk1,n1==Θks,ns=Θk,n, s2 are available. This paper's second goal is to implement this theory and provide evidence for it through numerical experiments and a suitable spline error analysis. Specifically, we provide a method that can compute υk(Pn(Ω,Φ) with low computational cost and high degree of accuracy. The method is comparable to the extrapolation process used in Romberg integration to produce high-precision integral estimates from a small number of imprecise trapezoidal approximations. This is where the Euler-Maclaurin formula and the asymptotic expansion (1.3) come into play.

    Throughout the entire work, we make use of the following parameters: Step size Λ=1/(n+1), for certain positive integers nN, and the grid points Θ=kπΛ,k=1,2,3,n. We make some assumptions and employ expansion (1.3) throughout this section:

    ● The RCTPs are Ω,Φ,r, and they increase monotonically.

    ● Suppose that α and n(1),nN, are fixed parameters.

    ● Either nj=mj1(n(1)+1)1 or nj are selected at random.

    ● Give definitions to the PBST matrix sequences Pnj(Ω,Φ).

    ● Determine the eigenvalues of each and every PBST matrix, Pnj(Ω,Φ).

    This algorithm is intended to compute the eigenvalues of the Pn(Ω,Φ) when n is very large, which are very difficult to compute by the standard eigensolver (e.g., MATLAB function, 'eig'). Therefore, in order to expedite computation, we compute the eigenvalues of the Pn1,Pn2,,Pns, for small nj by the eigensolver. Using these eigenvalues of the small size PBST matrices, we can evaluate the eigenvalues of the large size PBST matrix.

    Interpolation and extrapolation

    When Θj,n1=Θj,ns is fixed, we can compute the eigenvalues of all Pnj(Ω,Φ) and set them in Table 1 against Λj as

    Table 1.  Eigenvalues of Pnj matrices according to s.
    Λ1 υ1,1 υ2,1 υn1,1
    Λ2 υ1,2 υ2,2 υn2,2
    Λ3 υ1,3 υ2,3 υn3,3
    Λs υ1,s υ2,s υns,s

     | Show Table
    DownLoad: CSV

    Every collection of eigenvalues needs to have a grid attached to it. In order to define the grid, we define Θnj,k=kΛjπ for k=1,2,3,,nj, and Λj=1nj+1. For k=1,2,3,nβ, the Θ-grid of the Pnβ(Ω,Φ) is Θnβ,j=jΛπ. For j=1,2,3,,s, the number of eigenvalues in Pnβ(Ω,Φ) is significantly more than that in Pnj(Ω,Φ). For each set of eigenvalues of size nj, j=1,2,3,,s attached to Θ-grid Θnj,k, k=1,2,3,,nβ, we interpolate and extrapolate the nβ-eigenvalues before doing the extrapolation k=nj,,1,2,3. We apply a higher-order spline-curve fitting for all Θ-grids in order to attain the higher order of precision in the interpolation and extrapolation of eigenvalues. For the interior Θ-grid node, the suggested higher-order spline fitting performs well; nevertheless, performance degrades toward the grid's edge. We apply lower-order shape-preserving spline curve fitting to solve this issue.

    After all Θ-grids have been interpolated and extrapolated, we perform one last extrapolation to obtain the eigenvalues of Pnβ(Ω,Φ). We have all of the interpolated and extrapolated eigenvalues of the PBST matrices Pnj(Ω,Φ). We can now compute the ˜ζk(Θnj,j) using these eigenvalues. We extend the expansion (1.3) for α=4 in order to achieve this.

    υk(Pn(Ω,Φ))=r(Θk,n)+ζ1(Θk,n)h+ζ2(Θk,n)Λ2+ζ3(Θk,n)Λ3+ζ4(Θk,n)Λ4+ϵk,n,4,ϵk,n,0=υk(Pn(Ω,Φ))r(Θk,n)=ζ1(Θk,n)h+ζ2(Θk,n)Λ2+ζ3(Θk,n)Λ3+ζ4(Θk,n)Λ4+ϵk,n,4. (2.1)

    Set nj, j{1,2,3,4} for any positive integers m and nj, then satisfy nj=mj1(n(1)+1)1 or pick nj randomly. The expansion (2.1) for the four matrices of nj is as follows:

    ϵk1,n1,0=ζ1(Θk1,n1)Λ1+ζ2(Θk1,n1)Λ21+ζ3(Θk1,n1)Λ31+ζ4(Θk1,n1)Λ41+ϵk1,n1,4,ϵk2,n2,0=ζ1(Θk2,n2)Λ2+ζ2(Θk2,n2)Λ22+ζ3(Θk2,n1)Λ32+ζ4(Θk2,n1)Λ42+ϵk2,n2,4,ϵk3,n3,0=ζ1(Θk3,n3)Λ3+ζ2(Θk3,n3)Λ23+ζ3(Θk3,n1)Λ33+ζ4(Θk3,n1)Λ43+ϵk3,n3,4,ϵk4,n4,0=ζ1(Θk4,n4)Λ4+ζ2(Θk4,n4)Λ24+ζ3(Θk4,n1)Λ34+ζ4(Θk4,n1)Λ44+ϵk4,n4,4. (2.2)

    Observe that Θki,ni=Θk1,n1=ˉΘ for k1{1,2,,n1} where Λi=1ni+1. The numerical estimate of ζj(ˉΘ) for j{1,2,3,4} is of interest to us. The set of Eq (2.2) becomes

    ϵk1,n1,0=˜ζ1(ˉΘ)Λ1+˜ζ2(ˉΘ)Λ21+˜ζ3(ˉΘ)Λ31+˜ζ4(ˉΘ)Λ1ϵk2,n2,0=˜ζ1(ˉΘ)Λ2+˜ζ2(ˉΘ)Λ22+˜ζ3(ˉΘ)Λ32+˜ζ4(ˉΘ)Λ2ϵk3,n3,0=˜ζ1(ˉΘ)Λ3+˜ζ2(ˉΘ)Λ23+˜ζ3(ˉΘ)Λ33+˜ζ4(ˉΘ)Λ3ϵk4,n4,0=˜ζ1(ˉΘ)Λ4+˜ζ2(ˉΘ)Λ24+˜ζ3(ˉΘ)Λ34+˜ζ4(ˉΘ)Λ4. (2.3)

    For k11,2,,n1, we solve the aforementioned system of linear equations to obtain ˜ζk(ˉΘ). The big size nβ matrix's eigenvalues are estimated using the computed ˜ζj by utilizing

    ˜υk(Pnβ(Ω,Φ))=r(Θk,nβ)+Λnβ˜ζ.

    References for the error bounds of \(\zeta_k\) in the asymptotic expansion are provided in [5].

    Finding all of the eigenvalues of the large-size PBST matrices is the primary goal of the numerical algorithm. Using conventional eigenvalue solvers such as the 'eig' function in MATLAB, we can obtain the spectrum information of smaller PBST matrices. The generating symbol is the quotient of RCTPs since we are working with PBST matrices. In order for the suggested technique to achieve high accuracy in the numerically computed eigenvalues, the generating symbol's monotonicity is essential. The algorithm remains functional even when dealing with non-monotonically generated symbols; however, the non-monotonic part's numerical accuracy suffers as a result.

    Let {Pn(Ω,Φ)=T1n(Φ)Tn(Ω)} be a sequence of preconditioned symmetric banded Toeplitz matrices. For k=n1,n2,n3,ns, we select a collection of Pk(Ω,Φ). The total number of small size Pk(Ω,Φ) is denoted by s in this case. Furthermore, the nj are ordered as follows: n1<n2<n3<<ns. We do not impose any stringent requirements on selecting nj's, but careful selection can raise the accuracy of our numerical findings. We might calculate the eigenvalues of Pnj(Ω,Φ) for each nj. For i=1,2,3,,s, we have s-sets of eigenvalues with sizes nj. Assume that nβ is a huge number and that we are interested in calculating the spectrum of a large size Pnβ(Ω,Φ). Every collection of eigenvalues needs to have a grid attached to it. In order to define the grid, we define Θnj,k=kΛjπ for k=1,2,3,,nj, and Λj=1nj+1. For k=1,2,3,nβ, the Θ-grid of the Pnβ(Ω,Φ) is Θnβ,j=jΛπ.

    For j=1,2,3,,s, the number of eigenvalues in Pnβ(Ω,Φ) is significantly more than that in Pnj(Ω,Φ). For each set of eigenvalues of size nj, j=1,2,3,,s attached to Θ-grid Θnj,k, k=1,2,3,,nβ, we interpolate and extrapolate the nβ-eigenvalues before doing the extrapolation. We employ higher-order spline-curve fitting across all \(\Theta\)-grids to achieve greater precision in interpolating and extrapolating eigenvalues. For nodes within the \(\Theta\)-grid, this advanced spline fitting shows commendable performance; however, its efficacy diminishes near the grid's boundaries. To address this, we resort to lower-order, shape-preserving spline fitting. Once interpolation and extrapolation are completed for all \(\Theta\)-grids, a final extrapolation step is undertaken to ascertain the eigenvalues of \({\mathcal P}_{n_\beta}(\Omega, \Phi)\).

    It is worth mentioning that Bogoya et al. [6] recently published an article introducing a new algorithm that can accurately interpolate and extrapolate the spectrum of preconditioned Toeplitz matrix sequences at machine level accuracy. The approach described by Bogoya et al. [6] differs from the current idea, primarily in that it requires the generating symbol to be directly inverted. Alternatively, one can solve a nonlinear equation to get the inversely projected values; however, our current methodology does not require this step.

    An algorithm for extracting particular eigenvalues from huge preconditioned matrices generated from a sequence of preconditioned Toeplitz matrices was published by Fayyaz et al. [5]. Our current work is novel since we can extrapolate and interpolate the whole spectrum. One limitation of our strategy is that it necessitates the use of two different kinds of smoothing-spline methods, particularly in proximity to boundaries where a shape-preserving smoothing-spline approach is required.

    Here we perform numerical testing on a collection of problems taken from the paper of Ekström et al. [7]. We assume Θ[0,π] and Ω(Θ)>0,Θ[0,π], Φ(0)0, for all of our numerical testing.

    Example 1. Consider the monotonic rising functions Ω, Φ, and r, which are defined as

    Ω(Θ)=1,Φ(Θ)=68cos(Θ)+2cos(2Θ),r(Θ)=Φ(Θ)Ω(Θ)=68cos(Θ)+2cos(2Θ).

    For n=5000,n(1)=10, and s=7, we wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r). The error between eigenvalues υn and an approximated eigenvalues ~υn is displayed in Figure 1, when compared to Θj,n,j=1,2,3,,n. The graph illustrates the compression between two algorithms, the first of which presented in [7]. Compared to the Erik Algorithm [7], our proposed technique is faster and more accurate, as shown by the Figure 1.

    Figure 1.  log10(Error), in the case n=5000, n(1)=10, and s=7 for Example 1.

    Example 2. Let the monotonic rising functions Ω, Φ, and r be defined as

    Ω(Θ)=1,Φ(Θ)=68cos(Θ)+2cos(2Θ),r(Θ)=Φ(Θ)Ω(Θ)=68cos(Θ)+2cos(2Θ).

    For n=10000,n(1)=10, and s=7, we wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r). The error between the approximated eigenvalues ~υn and the eigenvalues υn is displayed in Figure 2 in relation to Θj,n,j=1,2,3,,n. The graph indicates that our algorithm's accuracy increases as the target matrix's size increases, with values above machine zero.

    Figure 2.  log10(Error), in the case n=10000, n(1)=10, and s=7 for Example 2.

    Example 3. Let the monotonic rising functions Ω, Φ, and r be described as

    Ω(Θ)=1,Φ(Θ)=1412cos(Θ)+14cos(2Θ)112cos(3Θ),r(Θ)=Φ(Θ)Ω(Θ)=1412cos(Θ)+14cos(2Θ)112cos(3Θ),

    For n=10000,n(1)=10, and s=5, we wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r). The error between the eigenvalues υn and the approximated eigenvalues ~υn versus Θj,n,j=1,2,3,,n, is shown in Figure 3. When we increase the value of s, it means the sequence of the PBST matrices increases. We can observe this immediately.

    Figure 3.  log10(Error), in the case n=10000, n(1)=10, and s=5 for Example 3.

    Example 4. Let the monotonic rising functions Ω, Φ, and r be described as

    Ω(Θ)=1,Φ(Θ)=301400+15cos(Θ)+15cos(2Θ)+110cos(3Θ)120cos(4Θ)+1400cos(6Θ),r(Θ)=Φ(Θ)Ω(Θ)=301400+15cos(Θ)+15cos(2Θ)+110cos(3Θ)120cos(4Θ)+1400cos(6Θ).

    Next, the eigenvalues of υn=Tn(Ω)1TnΦ=Tn(r) are approximated for n=10000,n(1)=10, and s=7. The error between the eigenvalues υn and the approximated eigenvalues ~υn versus Θj,n,j=1,2,3,,n, is virtually minimum from Example 4 in [7], as we can see in Figure 4. Our algorithm errors are quickly evaluated and range from 109 to over 1016.

    Figure 4.  log10(Error), in the case n=10000, n(1)=10, and s=7 for Example 4.

    Example 5. Consider the monotonic rising functions Ω, Φ, and r, which are defined as

    Ω(Θ)=1,Φ(Θ)=301400+15cos(Θ)+15cos(2Θ)+110cos(3Θ)120cos(4Θ)+1400cos(6Θ),r(Θ)=Φ(Θ)Ω(Θ)=301400+15cos(Θ)+15cos(2Θ)+110cos(3Θ)120cos(4Θ)+1400cos(6Θ).

    We wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r) for n=10000,n(1)=25, and s=7. The error between the estimated eigenvalues ~υn and the eigenvalues υn is displayed in Figure 5 in relation to Θj,n,j=1,2,3,,n. The lowest error is obtained for Θj,n when j[500,4500].

    Figure 5.  log10(Error), in the case n=10000, n(1)=25, and s=7 for Example 5.

    Example 6. Let the monotonic rising functions Ω, Φ, and r be defined as

    Ω(Θ)=3+2cos(Θ),Φ(Θ)=2cos(Θ)cos(2Θ),r(Θ)=Ω(Θ)Φ(Θ)=2cos(Θ)cos(2Θ)3+2cos(Θ).

    We wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r) where r=Φ/Ω for n=5000,n(1)=50, and s=4. The error between the estimated eigenvalues ~υn and the eigenvalues υn is displayed in Figure 6 in relation to Θj,n,j=1,2,3,,n. The lowest error is obtained for Θj,n when j[500,4500]. The discrepancy between the eigenvalues can be observed by varying the parameters and producing functions that are more adequate for all instances, as demonstrated in Examples 1 to 5 when Ω(Θ) is similar. These codes are found in [7]. As we can see in Figure 6, there are more errors than machine zeros in case 6, where Ω(Θ) is not identical. When both Φ(Θ) and Ω(Θ) are not equal, our algorithm performed most accurately.

    Figure 6.  log10(Error), in the case n=5000, n(1)=50, and s=4 for Example 6.
    Table 2.  Example 6. CPU time, in the case Ω(Θ)=3+2cos(Θ),Φ(Θ)=2cos(Θ)cos(2Θ).
    Parameters Erik Algorithm [7](Time) Proposed Algorithm(Time)
    s=4,n=5000,n(1)=50 13.3093 0.8154
    s=4,n=5000,n(1)=100 12.8770 1.6483
    s=4,n=5000,n(1)=200 18.8837 3.9735
    s=4,n=5000,n(1)=400 25.7752 14.0923
    MATLAB's eig function 44.9260 41.1051

     | Show Table
    DownLoad: CSV

    Example 7. Let the monotonic rising functions Ω, Φ, and r be defined as

    Ω(Θ)=1208+1191cos(Θ)+120cos(2Θ)+cos(3Θ),Φ(Θ)=4015cos(Θ)24cos(2Θ)cos(3Θ),r(Θ)=Ω(Θ)Φ(Θ)=4015cos(Θ)24cos(2Θ)cos(3Θ)1208+1191cos(Θ)+120cos(2Θ)+cos(3Θ).

    We wish to approximate the eigenvalues of the υn=Tn(Ω)1TnΦ=Tn(r) for n=5000,n(1)=50, and s=4. In Figure 7, the error between the eigenvalues υn and an approximated eigenvalues ~υn versus Θnβ,j,j=1,2,3,,nβ shows the minimum error inside of the boundary, and the maximum near the boundary, but we achieve the minimum error, more specifically the machine zero, demonstrating the high accuracy and speed of our proposed algorithm in comparison to that of Ekström [7].

    Figure 7.  log10(Error), in the case n=5000, n(1)=50, and s=4 for Example 7.

    In this work, we present an algorithm to calculate the eigenvalues of matrices extracted from a sequence of large-scale Toeplitz matrices that are preconditioned banded symmetric (PBST). When compared to existing eigenvalue solvers, computing the eigenvalues of large-size PBST matrices should be more economical. We collect all the spectrum information of small-size Toeplitz PBST matrices while taking the algorithm's computing cost into consideration. The reciprocal sizes of smaller PBST matrices can be used to sort their spectral information. Depending on the size of the PBST matrix, the monotonic spectrum arrangement can be arranged in bijection with an appropriate grid. For the large-size grid connected to the large-size PBST, we are able to interpolate and extrapolate the eigenvalue of the small-size PBST. Now, all of the small PBSTs have the same size spectrum. Finally, we use the extrapolation method---in our case, higher-order spline fitting---to compute the spectrum of the large-size PBST.

    Salima Kouser: Methodology, Writing- Original draft preparation. Shafiq Ur Rehman: Conceptualization, Supervision. Mabkhoot Alsaiari: Investigation, Formal analysis. Fayyaz Ahmad: Software, Validation. Mohammed Jalalah: Visualization, Resources, Funding acquisition. Farid A. Harraz: Data curation, Writing - Review & editing. Muhammad Akram: Project administration, Writing - Review & editing.

    The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

    The authors are grateful to the Deanship of Scientific Research at Najran University for funding this work under the Research Groups Funding Programme grant code (NU/RG/SERC/12/23).

    The authors declare that there is no conflict of interest regarding the publication of this paper.



    [1] J. Stoer, R. Bulirsch, R. Bartels, W. Gautschi, C. Witzgall, Introduction to numerical analysis, Springer-Verlag, New York, 2 (1980).
    [2] P. Tilli, A note on the spectral distribution of Toeplitz matrices, Linear Multilinear A., 45 (1998), 147–159. https://doi.org/10.1080/03081089808818584 doi: 10.1080/03081089808818584
    [3] O. Toeplitz, Zur Theorie der quadratischen und bilinearen Formen von unendlichvielen Veriinderlichen, Theorie der L-Formen, 70 (1911), 351–376. https://doi.org/10.1007/BF01564502
    [4] U. Grenander, G. Szego, Toeplitz forms and their applications, 2Eds., Chelsea, New York, 1984.
    [5] F. Ahmad, E. S. Al-Aidarous, D. A. Alrehaili, S. E. Ekström, I. Furci, S. Serra-Capizzano, Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form? Numer. Algorithms, 78 (2018), 867–893. https://doi.org/10.1007/s11075-017-0404-z doi: 10.1007/s11075-017-0404-z
    [6] M. Bogoya, S. Serra-Capizzano, P. Vassalos, Fast Toeplitz eigenvalue computations, joining interpolation-extrapolation matrix-less algorithms and simple-loop theory: The preconditioned setting, Appl. Math. Comput., 466 (2024), 128483. https://doi.org/10.1016/j.amc.2023.128483 doi: 10.1016/j.amc.2023.128483
    [7] S. E. Ekström, C. Garoni, A matrix-less and parallel interpolation-extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices, Numer. Algorithms, 80 (2019), 819–848.
    [8] M. Barrera, S. M. Grudsky, Asymptotics of eigenvalues for pentadiagonal symmetric Toeplitz matrices, in Large Truncated Toeplitz Matrices, Toeplitz Operators, and Related Topics: The Albrecht Böttcher Anniversary Volume, 2017, 51–77. https://doi.org/10.1007/978-3-319-49182-0_7
    [9] F. L. Bauer, H. Rutishauser, E. Stiefel, New aspects in numerical quadrature, Proc. Symp. Appl. Math., 15 (1963), 199–218. https://doi.org/10.1090/psapm/015/0174177 doi: 10.1090/psapm/015/0174177
    [10] R. Bevilacqua, D. A. Bini, M. Capovani, O. Menchi, Metodi numerici, Zanichelli, Bologna, 1992.
    [11] D. Bini, M. Capovani, Spectral and computational properties of band symmetric Toeplitz matrices, Linear Algebra Appl., 52 (1983), 99–126. https://doi.org/10.1016/0024-3795(83)80009-3 doi: 10.1016/0024-3795(83)80009-3
    [12] D. A. Bini, M. Capovani, O. Menchi, Metodi numerici per l'algebra lineare, 1988.
    [13] J. M. Bogoya, A. Böttcher, E. A. Maximenko, From convergence in distribution to uniform convergence, Bol. Soc. Mat. Mex., 22 (2016), 695–710. https://doi.org/10.1007/s40590-016-0105-y doi: 10.1007/s40590-016-0105-y
    [14] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maximenko, Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols, J. Math. Anal. Appl., 422 (2015), 1308–1334. https://doi.org/10.1016/j.jmaa.2014.09.057 doi: 10.1016/j.jmaa.2014.09.057
    [15] J. M. Bogoya, A. Böttcher, S. M. Grudsky, E. A. Maximenko, Maximum norm versions of the Szegő and Avram-Parter theorems for Toeplitz matrices, J. Approx. Theory, 196 (2015), 79–100. https://doi.org/10.1016/j.jat.2015.03.003 doi: 10.1016/j.jat.2015.03.003
    [16] J. M. Bogoya, S. M. Grudsky, E. A. Maximenko, Eigenvalues of Hermitian Toeplitz matrices generated by simple-loop symbols with relaxed smoothness, in Large Truncated Toeplitz Matrices, Toeplitz Operators, and Related Topics: The Albrecht Böttcher Anniversary Volume, 2017,179–212. https://doi.org/10.1007/978-3-319-49182-0_11
    [17] A. Böttcher, S. M. Grudsky, E. A. Maksimenko, Inside the eigenvalues of certain Hermitian Toeplitz band matrices, J. Comput. Appl. Math., 233 (2010), 2245–2264. https://doi.org/10.1016/j.cam.2009.10.010 doi: 10.1016/j.cam.2009.10.010
    [18] A. Böttcher, B. Silbermann, Introduction to large truncated Toeplitz matrices, Springer, New York, 1999. https://doi.org/10.1007/978-1-4612-1426-7
    [19] C. Brezinski, M. R. Zaglia, Extrapolation methods: Theory and practice, Elsevier, Amsterdam, 1991.
    [20] R. H. Chan, M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38 (1996), 427–482. https://doi.org/10.1137/S0036144594276474 doi: 10.1137/S0036144594276474
    [21] F. Di Benedetto, G. Fiorentino, S. Serra-Capizzano, CG preconditioning for Toeplitz matrices, Comput. Math. Appl., 25 (1993), 35–45. https://doi.org/10.1016/0898-1221(93)90297-9 doi: 10.1016/0898-1221(93)90297-9
    [22] S. E. Ekström, C. Garoni, S. Serra-Capizzano, Are the eigenvalues of banded symmetric Toeplitz matrices known in almost closed form? Exp. Math., 27 (2018), 478–487. https://doi.org/10.1080/10586458.2017.1320241 doi: 10.1080/10586458.2017.1320241
    [23] S. Serra-Capizzano, On the extreme spectral properties of Toeplitz matrices generated by L1 functions with several minima/maxima, BIT, 36 (1996), 135–142. https://doi.org/10.1007/BF01740550 doi: 10.1007/BF01740550
    [24] S. Serra-Capizzano, An ergodic theorem for classes of preconditioned matrices, Linear Algebra Appl., 282 (1998), 161–183. https://doi.org/10.1016/S0024-3795(98)80002-5 doi: 10.1016/S0024-3795(98)80002-5
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1184) PDF downloads(84) Cited by(0)

Figures and Tables

Figures(7)  /  Tables(2)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog