Efficient Construction of Fiedler and Generalized Fiedler Linearizations via Algorithmic Method

Eigenvalue problems, especially polynomial and rational eigenvalue problems, are encountered in a wide range of applications. Linearization is a method where the eigenvalue problems convert to a linear eigenvalue problem and the later ne can be easily solved via many well known algorithms. Among the various kind of linearizations, Fiedler and generalized Fiedler linearizations are particularly important to handle the issue as they are easy <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex> construct and attend some structures if the matrices have any structure. However, traditional approaches to constructing these linearizations involve matrix multiplications, which can be computationally costly and challenging to implement practically. In this article, we propose algorithms for generating the Fiedler linearizations and generalized linearizations without the need for explicit multiplication of elementary and Fiedler matrices. These algorithms offer a more efficient and robust construction process. The proposed algorithms can be extended to deal with rational eigenvalue problems. Our algorithms have the potential in developing computational toolboxes for further studies in eigenvalue problems.