Selecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations
Title | Selecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations |
Publication Type | Conference Paper |
Year of Publication | 2016 |
Authors | Eberly, Wayne |
Conference Name | Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation |
Publisher | ACM |
Conference Location | New York, NY, USA |
ISBN Number | 978-1-4503-4380-0 |
Keywords | black 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. |
URL | http://doi.acm.org/10.1145/2930889.2930894 |
DOI | 10.1145/2930889.2930894 |
Citation Key | eberly_selecting_2016 |