Visible to the public Selecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations

TitleSelecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations
Publication TypeConference Paper
Year of Publication2016
AuthorsEberly, Wayne
Conference NameProceedings of the ACM on International Symposium on Symbolic and Algebraic Computation
PublisherACM
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4380-0
Keywordsblack box, black box encryption, black box matrix computations, certificates, composability, cryptography, Encryption, Metrics, pubcrawl, Resiliency, selection of algorithms, sparse and structured matrices
Abstract

Processes to automate the selection of appropriate algorithms for various matrix computations are described. In particular, processes to check for, and certify, various matrix properties of black-box matrices are presented. These include sparsity patterns and structural properties that allow "superfast" algorithms to be used in place of black-box algorithms. Matrix properties that hold generically, and allow the use of matrix preconditioning to be reduced or eliminated, can also be checked for and certified -- notably including in the small-field case, where this presently has the greatest impact on the efficiency of the computation.

URLhttp://doi.acm.org/10.1145/2930889.2930894
DOI10.1145/2930889.2930894
Citation Keyeberly_selecting_2016