Fast algorithms for finding the solution of CUPL-Toeplitz linear system from Markov chain

被引：21

作者：

Fu, Yaru ^{[1
,2
]}

Jiang, Xiaoyu ^{[3
]}

Jiang, Zhaolin ^{[1
]}

Jhang, Seongtae ^{[2
]}

机构：

[1] Linyi Univ, Sch Math & Stat, Linyi 276000, Shandong, Peoples R China

[2] Univ Suwon, Coll Informat Technol, Hwaseong Si 445743, South Korea

[3] Linyi Univ, Sch Informat Sci & Technol, Linyi 276000, Shandong, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2021年 / 396卷 / 396期

基金：

中国国家自然科学基金;

关键词：

CUPL-Toeplitz linear system; Markov chain; Sherman-Morrison-Woodbury formula; Toeplitz matrix; Low rank matrix; CYCLIC DISPLACEMENTS; MATRICES;

D O I：

10.1016/j.amc.2020.125859

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, the nonsingular CUPL-Toeplitz linear system from Markov chain is solved. We introduce two fast approaches whose complexity could be considered to be O(n log n) based on the splitting method of the CUPL-Toeplitz matrix which equals to a Toeplitz matrix minus a rank-one matrix. Finally, we confirm the performance of the new algorithms by three numerical experiments. (C) 2020 Published by Elsevier Inc.

引用

页数：4

共 16 条

[1] The use of the Sherman-Morrison-Woodbury formula to solve cyclic block tri-diagonal and cyclic block penta-diagonal linear systems of equations [J].

Batista, Milan ;

Karawia, Abdel Rahman A. Ibrahim .

APPLIED MATHEMATICS AND COMPUTATION, 2009, 210 (02) :558-563

[2] Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox [J].

Bini, Dario A. ;

Massei, Stefano ;

Robol, Leonardo .

NUMERICAL ALGORITHMS, 2019, 81 (02) :741-769

[3] On the exponential of semi-infinite quasi-Toeplitz matrices [J].

Bini, Dario A. ;

Meini, Beatrice .

NUMERISCHE MATHEMATIK, 2019, 141 (02) :319-351

[4] SEMI-INFINITE QUASI-TOEPLITZ MATRICES WITH APPLICATIONS TO QBD STOCHASTIC PROCESSES [J].

Bini, Dario A. ;

Massei, Stefano ;

Meini, Beatrice .

MATHEMATICS OF COMPUTATION, 2018, 87 (314) :2811-2830

[5]

[Бини Дарио Андреа Bini Dario Andrea], 2017, [Математический сборник, Sbornik: Mathematics, Matematicheskii sbornik], V208, P56, DOI 10.4213/sm8864

[6] A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems [J].

Du, Lei ;

Sogabe, Tomohiro ;

Zhang, Shao-Liang .

APPLIED MATHEMATICS LETTERS, 2018, 75 :74-81

[7] A fast numerical method for block lower triangular Toeplitz with dense Toeplitz blocks system with applications to time-space fractional diffusion equations [J].

Huang, Yun-Chi ;

Lei, Siu-Long .

NUMERICAL ALGORITHMS, 2017, 76 (03) :605-616

[8] Skew cyclic displacements and inversions of two innovative patterned Matrices [J].

Jiang, Xiaoyu ;

Hong, Kicheon .

APPLIED MATHEMATICS AND COMPUTATION, 2017, 308 :174-184

[9] The Explicit Inverses of CUPL-Toeplitz and CUPL-Hankel Matrices [J].

Jiang, Zhao-Lin ;

Chen, Xiao-Ting ;

Wang, Jian-Min .

EAST ASIAN JOURNAL ON APPLIED MATHEMATICS, 2017, 7 (01) :38-54

[10]

Jin X.-Q., 2010, Preconditioning Techniques for Toeplitz Systems

← 1 2 →