Integer Levinson Algorithm for the Inversion of Any Nonsingular Hermitian Toeplitz Matrix
Y. Bistritz, Idan Dekel · IEEE Transactions on Information Theory · 2024
This paper presents an integer preserving (IP) version of the Levinson algorithm to solve a normal set of equations for a Hermitian Toeplitz matrix with any singularity profile. The IP property means that for a matrix with integer entries, the algorithm can be completed over the integer solely by using a ring of integer operations. The IP algorithm provides remedies for unpredictable numerical outcomes when a corresponding floating-point (FP) Levinson algorithm either overlooks zero principal minors (PMs) or applies a singularity skipping routine to a PM that is considered erroneously to be zero. The error-free computational edge of integer arithmetic is also applicable to a non-integer Toeplitz matrix by first scaling it up to an acceptably accurate integer matrix. The proposed algorithm can also be used to obtain the inverse of a nonsingular Hermitian Toeplitz matrix (with any singularity profile) by one of two proposed IP Gohberg-Semencul type inversion formulas.