Matrix Polynomials

Since its inception, the theory of matrix polynomials has been strongly influenced by its applications to differential equations and vibrating systems. In fact, vibrating systems motivated the first works devoted primarily to matrix polynomials: one by Frazer, Duncan, and Collar in 1938~\cite{Frazer1955} and the other by Lancaster in 1966~\cite{Lancaster1966}. In addition, the theory of matrix polynomials has been influenced by results from matrix theory and complex analysis. The canonical set of Jordan chains defined in~\cite{Gohberg2009} are a natural generalization of a cycle of generalized eigenvectors, which are defined in~\cite{Friedberg2003}. A generalized Rouch\'e's theorem is presented in~\cite{Gohberg1990} and this result is used to prove a generalized Pellet's theorem for matrix polynomials~\cite{Melman2013}. These generalizations have benefited our study of matrix polynomials and their spectra, and it is in this spirit that we have focused on similar generalizations from matrix theory and complex analysis.

In~\cite{Cameron2015}, we use the generalized Rouch\'e theorem to provide spectral bounds for unitary matrix polynomials. This result can be viewed as a generalization of the fact that the eigenvalues of a unitary matrix lie on the unit circle or the fact that a scalar polynomial with unimodular coefficients has roots that lie in the annulus with inner radius 1/2 and outer radius 2.

In~\cite{Cameron2016}, we use a pseudo inner product to provide a constructive proof that every matrix polynomial can be reduced to a matrix rational in Hessenberg form. In general, an a priori reduction of a matrix polynomial to a simpler form can be used to reduce the cost of computing its eigenvalues. For additional methods capable of reducing a matrix polynomial to a simpler form, see~\cite{Nakatsukasa2018}.

In~\cite{Cameron2018_DRSMP}, we present a generalization of Descartes' rule of signs for self-adjoint matrix polynomials whose coefficients are either positive or negative definite, or null. Our main result shows that this generalization holds under the additional assumption that the matrix polynomial is hyperbolic. Also, we prove special cases where the matrix polynomial is diagonalizable by congruence, or of degree three or less. We conjecture that this generalization holds for all self-adjoint matrix polynomials whose coefficients are either positive or negative definite, or null, and discuss what makes this open problem non-trivial.

In~\cite{Cameron2019_GH}, we present a generalization of Householder sets for matrix polynomials. After defining these sets, we analyze their topological and algebraic properties, which include containing all of the eigenvalues of a given matrix polynomial. Finally, we show that these Householder sets are intimately connected with other inclusion sets, such as the Ger{\v s}gorin set and pseudospectra of a matrix polynomial, as well as with the Bauer-Fike theorem.

Numerical Analysis

Modern-day polynomial root problems, such as those that stem from computer algebra applications or digital signal processing, require software that can solve for the roots of a polynomial of degree well above $100$ and sometimes on the order of several thousand or higher~\cite{Pan1997,Sitton2003}. For this reason, root solvers that use an explicit deflation strategy, such as \emph{zroots}~\cite{Press} from Numerical Recipes and \emph{C02AFF}~\cite{NAG} from the NAG library, are not applicable for solving today's large degree polynomial equations.

In~\cite{Cameron2018_PML}, we employ a modification of Laguerre's method that was originally proposed in~\cite{Petkovic1997}. This method has strong virtues including the ability to compute all roots of a large degree polynomial, a local fourth-order convergence rate that can be observed in practice, and a workload that is well-suited for data-parallelism. We use this method to form an algorithm for the computation of all roots of a polynomial. Our algorithm is implemented in Fortran 90 using a double-precision floating-point format and is available at~\url{https://github.com/trcameron/FPML}.

In~\cite{Cameron2018_FPT}, we present a lively treatment of the floating-point format, the IEEE 754 standard, and compensated arithmetic techniques. This work was motivated by a current student project where we are working to improve the accuracy and speed of our root solver software~\cite{Cameron2018_PML} by using compensated arithmetic techniques and multithreading, respectively.

Current Research

Recently, I have applied my experience in numerical linear algebra and matrix polynomials to the research of the rankability of data and inhomogeneous Markov chains. The rankability of data is joint work with Paul Anderson, Tim Chartier, and Amy Langville, and inhomogeneous Markov chains is joint work with Michael J. Tsatsomeros.

Rankability of Data

The objective of ranking is to sort objects in a dataset according to some criterion. As a graph problem, we are finding the order or rank of vertices in a (weighted) directed graph. We are interested in defining a measure for the rankability of a data set, that is, the dataset's inherent ability to produce a meaningful ranking of its items.

If the directed graph is a perfect dominance graph, then there is a clear implied ranking. Therefore, the first proposed measure of rankability was based on the distance from a given graph to the nearest perfect dominance graph~\cite{Anderson2018}. This distance is measured by the number of changes, i.e., edges added or deleted, that would need to be made to the graph in order to change it into a perfect dominance graph. The exact rankability measure proposed in~\cite{Anderson2018} requires finding all optimal solutions of an integer or linear program, which is a difficult problem and not suitable for large datasets.

For this reason, we are interested in approximation methods for the above measure, or other methods for measuring rankability. Currently, we are looking into what information the SVD and graph Laplacian will provide on the rankability of a dataset. Just as with clusterability, we are likely to end up with many different ways of measuring rankability, each that focuses on a different aspect of what it means for a dataset to be rankable.

Students with a background in linear algebra or statistics can help our theoretical study outlined above. Those with a background in programming (e.g., in Mathematica, MATLAB, Python, or a related language) can help us investigate the rankability of datasets from applications such as recommendation systems, sports, and voting. Those with an advanced background in computer science can help us enhance these datasets through web scraping.

Inhomogeneous Markov Chains

Traditional homogeneous Markov chain models are broadly applied in different areas of ecology, such as behavioral sciences, conservation, and evolutionary and population dynamics. However, they are almost always based on a stationary assumption in the model. This stationary assumption has apparent limitations since ecological systems rarely remain stable under dynamic environmental conditions.

In our work, we consider time-inhomogeneous transition matrices $M(t)$ that are row stochastic as a function of time $t\geq 0$. With the additional assumption that the entries of $M(t)$ are polynomials in $t$, we can apply matrix polynomial theory to $(I-M(t))$ to study the left eigenvectors (the stationary distribution of the Markov chain as a function of time). Specifically, we can apply Perron-Frobenius theory and linearization techniques from~\cite{Mackey2006,Psarrakos2004} to our study of the left eigenvectors of $(I-M(t))$.

This work can be approached from many directions included nonnegative matrix theory and theory of matrix polynomials, as described above. Moreover, this project has a considerable number of applications in ecology, in particular the study of forest growth~\cite{Lienard2016,Pastor2005}. Finally, there is potential for student projects that include collecting data from an ecosystem, analyzing the data, and building models that describe the data and give us a better understanding of the selected ecosystem.