An Efficient Solution to Structured Optimization Problems using Recursive Matrices

Simple item page
dc.contributor.authorRückert, Dariusen_US
dc.contributor.authorStamminger, Marcen_US
dc.contributor.editorSteinberger, Markus and Foley, Timen_US
dc.date.accessioned2019-07-11T06:51:46Z
dc.date.available2019-07-11T06:51:46Z
dc.date.issued2019
dc.description.abstractWe present a linear algebra framework for structured matrices and general optimization problems. The matrices and matrix operations are defined recursively to efficiently capture complex structures and enable advanced compiler optimization. In addition to common dense and sparse matrix types, we define mixed matrices, which allow every element to be of a different type. Using mixed matrices, the low- and high-level structure of complex optimization problems can be encoded in a single type. This type is then analyzed at compile time by a recursive linear solver that picks the optimal algorithm for the given problem. For common computer vision problems, our system yields a speedup of 3-5 compared to other optimization frameworks. The BLAS performance is benchmarked against the MKL library. We achieve a significant speedup in block-SPMV and block-SPMM. This work is implemented and released open-source as a header-only extension to the C++ math library Eigen.en_US
dc.description.number8
dc.description.sectionheadersSimulation and Optimization
dc.description.seriesinformationComputer Graphics Forum
dc.description.volume38
dc.identifier.doi10.1111/cgf.13758
dc.identifier.issn1467-8659
dc.identifier.pages33-39
dc.identifier.urihttps://doi.org/10.1111/cgf.13758
dc.identifier.urihttps://diglib.eg.org:443/handle/10.1111/cgf13758
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectComputing methodologies
dc.subjectSymbolic and algebraic algorithms
dc.subjectLinear algebra algorithms
dc.subjectOptimization algorithms
dc.titleAn Efficient Solution to Structured Optimization Problems using Recursive Matricesen_US
Files
Collections
38-Issue 8
High-Performance Graphics 2019