Publication: On the Efficient Computation of Sparsity Patterns for Hessians
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

On the Efficient Computation of Sparsity Patterns for Hessians

- incollection -
 

Author(s)
Andrea Walther

Published in
Recent Advances in Algorithmic Differentiation

Editor(s)
Shaun Forth, Paul Hovland, Eric Phipps, Jean Utke, Andrea Walther

Year
2012

Publisher
Springer

Abstract
The exploitation of sparsity forms an important ingredient for the efficient solution of large-scale problems. For this purpose, this paper discusses two algorithms to detect the sparsity pattern of Hessians: An approach for the computation of exact sparsity patterns and a second one for the overestimation of sparsity patterns. For both algorithms, corresponding complexity results are stated. Subsequently, new data structures and set operations are presented yielding a new complexity result together with an alternative implementation of the exact approach. For several test problems, the obtained runtimes confirm the new theoretical result, i.e., a significant reduction in the runtime needed by the exact approach. A comparison with the runtime required for the overestimation of the sparsity pattern is included together with a corresponding discussion. Finally, possible directions for future research are stated.

Cross-References
Forth2012RAi

AD Theory and Techniques
Hessian, Sparsity

BibTeX
@INCOLLECTION{
         Walther2012OtE,
       title = "On the Efficient Computation of Sparsity Patterns for {H}essians",
       doi = "10.1007/978-3-642-30023-3_13",
       author = "Andrea Walther",
       abstract = "The exploitation of sparsity forms an important ingredient for the efficient
         solution of large-scale problems. For this purpose, this paper discusses two algorithms to detect
         the sparsity pattern of Hessians: An approach for the computation of exact sparsity patterns and a
         second one for the overestimation of sparsity patterns. For both algorithms, corresponding
         complexity results are stated. Subsequently, new data structures and set operations are presented
         yielding a new complexity result together with an alternative implementation of the exact approach.
         For several test problems, the obtained runtimes confirm the new theoretical result, i.e., a
         significant reduction in the runtime needed by the exact approach. A comparison with the runtime
         required for the overestimation of the sparsity pattern is included together with a corresponding
         discussion. Finally, possible directions for future research are stated.",
       pages = "139--149",
       crossref = "Forth2012RAi",
       booktitle = "Recent Advances in Algorithmic Differentiation",
       series = "Lecture Notes in Computational Science and Engineering",
       publisher = "Springer",
       address = "Berlin",
       volume = "87",
       editor = "Shaun Forth and Paul Hovland and Eric Phipps and Jean Utke and Andrea Walther",
       isbn = "978-3-540-68935-5",
       issn = "1439-7358",
       year = "2012",
       ad_theotech = "Hessian, Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)