Source author record

B. David Saunders

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Symbolic Computation Mathematical Software Software Engineering math.AC math.NA Numerical Analysis

Catalog footprint

Research overview

5works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Equivalences for Linearizations of Matrix Polynomials

One useful standard method to compute eigenvalues of matrix polynomials ${\bf P}(z) \in \mathbb{C}^{n\times n}[z]$ of degree at most $\ell$ in $z$ (denoted of grade $\ell$ , for short) is to first transform ${\bf P}(z)$ to an equivalent linear matrix polynomial ${\bf L}(z)=z{\bf B}-{\bf A}$ , called a companion pencil, where ${\bf A}$ and ${\bf B}$ are usually of larger dimension than ${\bf P}(z)$ but ${\bf L}(z)$ is now only of grade $1$ in $z$ . The eigenvalues and eigenvectors of ${\bf L}(z)$ can be computed numerically by, for instance, the QZ algorithm. The eigenvectors of ${\bf P}(z)$ , including those for infinite eigenvalues, can also be recovered from eigenvectors of ${\bf L}(z)$ if ${\bf L}(z)$ is what is called a "strong linearization" of ${\bf P}(z)$ . In this paper we show how to use algorithms for computing the Hermite Normal Form of a companion matrix for a scalar polynomial to direct the discovery of unimodular matrix polynomial cofactors ${\bf E}(z)$ and ${\bf F}(z)$ which, via the equation ${\bf E}(z){\bf L}(z){\bf F}(z) = \mathrm{diag}( {\bf P}(z), {\bf I}_n, \ldots, {\bf I}_n)$ , explicitly show the equivalence of ${\bf P}(z)$ and ${\bf L}(z)$ . By this method we give new explicit constructions for several linearizations using different polynomial bases. We contrast these new unimodular pairs with those constructed by strict equivalence, some of which are also new to this paper. We discuss the limitations of this experimental, computational discovery method of finding unimodular cofactors.

preprint2015arXiv

Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation

Blackbox algorithms for linear algebra problems start with projection of the sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such algorithms usually depend on the minimal polynomial of the resulting sequence being that of the given matrix. Here exact formulas are given for the probability that this occurs. They are based on the generalized Jordan normal form (direct sum of companion matrices of the elementary divisors) of the matrix. Sharp bounds follow from this for matrices of unknown elementary divisors. The bounds are valid for all finite field sizes and show that a small blocking factor can give high probability of success for all cardinalities and matrix dimensions.

preprint2014arXiv

Elements of Design for Containers and Solutions in the LinBox Library

We describe in this paper new design techniques used in the \cpp exact linear algebra library \linbox, intended to make the library safer and easier to use, while keeping it generic and efficient. First, we review the new simplified structure for containers, based on our \emph{founding scope allocation} model. We explain design choices and their impact on coding: unification of our matrix classes, clearer model for matrices and submatrices, \etc Then we present a variation of the \emph{strategy} design pattern that is comprised of a controller--plugin system: the controller (solution) chooses among plug-ins (algorithms) that always call back the controllers for subtasks. We give examples using the solution \mul. Finally we present a benchmark architecture that serves two purposes: Providing the user with easier ways to produce graphs; Creating a framework for automatically tuning the library and supporting regression testing.

preprint2012arXiv

Fast Computation of Smith Forms of Sparse Matrices Over Local Rings

We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the \emph{black-box} model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic. For an $\nxn$ matrix $A$ over the ring $\Fzfe$, where $f^e$ is a power of an irreducible polynomial $f \in \Fz$ of degree $d$ , our algorithm requires $\bigO(ηde^2n)$ operations in $\F$, where our black-box is assumed to require $\bigO(η)$ operations in $\F$ to compute a matrix-vector product by a vector over $\Fzfe$ (and $η$ is assumed greater than $\Pden$). The algorithm only requires additional storage for $\bigO(\Pden)$ elements of $\F$. In particular, if $η=\softO(\Pden)$, then our algorithm requires only $\softO(n^2d^2e^3)$ operations in $\F$, which is an improvement on known dense methods for small $d$ and $e$ . For the ring $\ZZ/p^e\ZZ$, where $p$ is a prime, we give an algorithm which is time- and memory-efficient when the number of nontrivial invariant factors is small. We describe a method for dimension reduction while preserving the invariant factors. The time complexity is essentially linear in $μn r e \log p,$ where $μ$ is the number of operations in $\ZZ/p\ZZ$ to evaluate the black-box (assumed greater than $n$ ) and $r$ is the total number of non-zero invariant factors. To avoid the practical cost of conditioning, we give a Monte Carlo certificate, which at low cost, provides either a high probability of success or a proof of failure. The quest for a time- and memory-efficient solution without restrictions on the number of nontrivial invariant factors remains open. We offer a conjecture which may contribute toward that end.

preprint2010arXiv

LinBox founding scope allocation, parallel building blocks, and separate compilation

To maximize efficiency in time and space, allocations and deallocations, in the exact linear algebra library \linbox, must always occur in the founding scope. This provides a simple lightweight allocation model. We present this model and its usage for the rebinding of matrices between different coefficient domains. We also present automatic tools to speed-up the compilation of template libraries and a software abstraction layer for the introduction of transparent parallelism at the algorithmic level.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.