Publication: Combining partial Jacobian computation and preconditioning: New heuristics, educational modules, and applications
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Combining partial Jacobian computation and preconditioning: New heuristics, educational modules, and applications

- Ph.D. thesis -
 

Author(s)
M. A. Rostami

Year
2017

Abstract
Solving problems originating from real-world applications is often based on the solution of a system of linear equations whose coefficient matrix is a large sparse Jacobian matrix. Hence, there is research to exploit the sparsity structure and to decrease the amount of storage. In contrast to full Jacobian computation in which all nonzero elements are to be determined, partial Jacobian computation is looking at a subset of these elements. Partial Jacobian computation can therefore be faster and more efficient than full Jacobian computation. Since Jacobian matrix-vector products are needed in iterative solvers, these types of linear systems can be efficiently solved using automatic differentiation. Determining these nonzero elements in full or partial Jacobian computations by automatic differentiation techniques can be modeled as graph coloring in the language of graph theory. On the other hand, preconditioning techniques are used to improve the convergence of iterative solvers and typically need access to all nonzero elements of the Jacobian matrix. So, a sparsification is applied to the Jacobian matrix before computing the preconditioner. The nonzero elements obtained from the sparsification are considered as the required elements in a restricted coloring. Lülfesmann (PhD thesis, RWTH Aachen University, 2012) introduced a procedure that selects a subset of the remaining nonrequired elements. The approach then adds this subset to the sparsified matrix such that neither fill-in is created nor an increase in the number of colors happens. This thesis consists of two parts. In the first part, we look at different ways to optimize the process of selecting these nonrequired elements. We introduce three new coloring heuristics and compare them with each other as well as with existing approaches. Also, we look at a particular case in which we consider only the diagonal elements as required elements. For this case, we generalize a previous result and introduce a new coloring heuristic. To evaluate our proposed heuristics in practice, we apply them to a problem from geoscience. Finally, we describe our new software package implementing these new heuristics. In the second part of this thesis, we introduce a collection of interactive educational modules to teach not only graph coloring, but also other concepts from combinatorial scientific computing in the classroom. These modules are designed to involve the students more thoroughly in the process of learning. At the end, we explain the design of this collection and outline its implementation.

AD Tools
ADiMat

AD Theory and Techniques
Sparsity, Teaching

BibTeX
@PHDTHESIS{
         Rostami2017CpJ,
       url = "http://d-nb.info/1142137856",
       abstract = "Solving problems originating from real-world applications is often based on the
         solution of a system of linear equations whose coefficient matrix is a large sparse Jacobian matrix.
         Hence, there is research to exploit the sparsity structure and to decrease the amount of storage. In
         contrast to full Jacobian computation in which all nonzero elements are to be determined, partial
         Jacobian computation is looking at a subset of these elements. Partial Jacobian computation can
         therefore be faster and more efficient than full Jacobian computation. Since Jacobian matrix-vector
         products are needed in iterative solvers, these types of linear systems can be efficiently solved
         using automatic differentiation. Determining these nonzero elements in full or partial Jacobian
         computations by automatic differentiation techniques can be modeled as graph coloring in the
         language of graph theory. On the other hand, preconditioning techniques are used to improve the
         convergence of iterative solvers and typically need access to all nonzero elements of the Jacobian
         matrix. So, a sparsification is applied to the Jacobian matrix before computing the preconditioner.
         The nonzero elements obtained from the sparsification are considered as the required elements in a
         restricted coloring. L{\"u}lfesmann (PhD thesis, RWTH Aachen University, 2012) introduced
         a procedure that selects a subset of the remaining nonrequired elements. The approach then adds this
         subset to the sparsified matrix such that neither fill-in is created nor an increase in the number
         of colors happens. This thesis consists of two parts. In the first part, we look at different ways
         to optimize the process of selecting these nonrequired elements. We introduce three new coloring
         heuristics and compare them with each other as well as with existing approaches. Also, we look at a
         particular case in which we consider only the diagonal elements as required elements. For this case,
         we generalize a previous result and introduce a new coloring heuristic. To evaluate our proposed
         heuristics in practice, we apply them to a problem from geoscience. Finally, we describe our new
         software package implementing these new heuristics. In the second part of this thesis, we introduce
         a collection of interactive educational modules to teach not only graph coloring, but also other
         concepts from combinatorial scientific computing in the classroom. These modules are designed to
         involve the students more thoroughly in the process of learning. At the end, we explain the design
         of this collection and outline its implementation.",
       author = "M. A. Rostami",
       title = "Combining partial {J}acobian computation and preconditioning: {N}ew heuristics,
         educational modules, and applications",
       school = "Department of Mathematics and Computer Science, Friedrich Schiller University Jena",
       year = "2017",
       type = "Dissertation",
       address = "Jena",
       note = "Also published by Cuvillier Verlag, G{\"o}ttingen",
       ad_tools = "ADiMat",
       ad_theotech = "Sparsity, Teaching"
}


back
  

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