Two fast algorithms for finding the solution of the lower Hessenberg quasi-Toeplitz linear system from Markov chain

Area of Science:

• Numerical analysis
• Computational mathematics
• Markov chain analysis

Background:

• Nonsingular lower Hessenberg quasi-Toeplitz linear systems are crucial in Markov chain analysis.
• Existing methods for solving these systems can be computationally intensive.

Purpose of the Study:

• To develop and present two fast algorithms for solving nonsingular lower Hessenberg quasi-Toeplitz linear systems.
• To analyze and confirm the computational complexity of the proposed algorithms.

Main Methods:

• Decomposition of lower Hessenberg quasi-Toeplitz matrices into a sum of a Toeplitz matrix and a rank-one matrix.
• Adoption of fast solvers for Toeplitz linear systems, involving O[Formula: see text] operators.
• Implementation and numerical evaluation of the two proposed algorithms.

Main Results:

• The two developed algorithms achieve a computational complexity of O[Formula: see text].
• Numerical results demonstrate the superiority of the new algorithms in terms of residual values and CPU time.
• The algorithms are confirmed to be accurate and efficient compared to existing methods.

Conclusions:

• The proposed algorithms provide a significant advancement in solving specific linear systems relevant to Markov chains.
• The O[Formula: see text] complexity offers substantial computational savings.
• These algorithms are accurate and efficient, making them valuable tools for researchers and practitioners in related fields.