21 Search Results for "Toledo, Sivan"


Document
Parallelization of Mapping Algorithms for Next Generation Sequencing Applications

Authors: Doruk Bozdag, Catalin C. Barbacioru, and Umit V. Catalyurek

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
With the advent of next-generation high throughput sequencing instruments, large volumes of short sequence data are generated at an unprecedented rate. Processing and analyzing these massive data requires overcoming several challenges. A particular challenge addressed in this abstract is the mapping of short sequences (reads) to a reference genome by allowing mismatches. This is a significantly time consuming combinatorial problem in many applications including whole-genome resequencing, targeted sequencing, transcriptome/small RNA, DNA methylation and ChiP sequencing, and takes time on the order of days using existing sequential techniques on large scale datasets. In this work, we introduce six parallelization methods each having different scalability characteristics to speedup short sequence mapping. We also address an associated load balancing problem that involves grouping nodes of a tree from different levels. This problem arises due to a trade-off between computational cost and granularity while partitioning the workload. We comparatively present the proposed parallelization methods and give theoretical cost models for each of them. Experimental results on real datasets demonstrate the effectiveness of the methods and indicate that they are successful at reducing the execution time from the order of days to under just a few hours for large datasets. To the best of our knowledge this is the first study on parallelization of short sequence mapping problem.

Cite as

Doruk Bozdag, Catalin C. Barbacioru, and Umit V. Catalyurek. Parallelization of Mapping Algorithms for Next Generation Sequencing Applications. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{bozdag_et_al:DagSemProc.09061.14,
  author =	{Bozdag, Doruk and Barbacioru, Catalin C. and Catalyurek, Umit V.},
  title =	{{Parallelization of Mapping Algorithms for Next Generation Sequencing Applications}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.14},
  URN =		{urn:nbn:de:0030-drops-21294},
  doi =		{10.4230/DagSemProc.09061.14},
  annote =	{Keywords: Genome sequencing, sequence mapping}
}
Document
Assessing an approximation algorithm for the minimum fill-in problem in practice

Authors: H. Martin Bücker, Michael Lülfesmann, and Arno Rasch

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
We investigate an implementation of an approximation algorithm for the minimum fill-in problem. The algorithm has some degree of freedom since it is composed of several subtasks for which one can choose between different algorithms. The goal of the present work is to study the impact of theses components and carefully examine the practicability of the overall approximation algorithm by a set of numerical examples.

Cite as

H. Martin Bücker, Michael Lülfesmann, and Arno Rasch. Assessing an approximation algorithm for the minimum fill-in problem in practice. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{bucker_et_al:DagSemProc.09061.5,
  author =	{B\"{u}cker, H. Martin and L\"{u}lfesmann, Michael and Rasch, Arno},
  title =	{{Assessing an approximation algorithm for the minimum fill-in problem in practice}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.5},
  URN =		{urn:nbn:de:0030-drops-21191},
  doi =		{10.4230/DagSemProc.09061.5},
  annote =	{Keywords: Sparse linear algebra}
}
Document
09061 Abstracts Collection – Combinatorial Scientific Computing

Authors: Uwe Naumann, Olaf Schenk, Horst D Simon, and Sivan Toledo

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
From 01.02.2009 to 06.02.2009, the Dagstuhl Seminar 09061 ``Combinatorial Scientific Computing '' was held in Schloss Dagstuhl – Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Uwe Naumann, Olaf Schenk, Horst D Simon, and Sivan Toledo. 09061 Abstracts Collection – Combinatorial Scientific Computing. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{naumann_et_al:DagSemProc.09061.1,
  author =	{Naumann, Uwe and Schenk, Olaf and Simon, Horst D and Toledo, Sivan},
  title =	{{09061 Abstracts Collection – Combinatorial Scientific Computing}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--49},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.1},
  URN =		{urn:nbn:de:0030-drops-21124},
  doi =		{10.4230/DagSemProc.09061.1},
  annote =	{Keywords: Graphs, combinatorics, high-performance scientific computing}
}
Document
A Model for Task Repartioning under Data Replication

Authors: Cevdet Aykanat, Erkan Okuyan, and B. Barla Cambazoglu

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
We propose a two-phase model for solving the problem of task repartitioning under data replication with memory constraints. The hypergraph-partitioning-based model proposed for the first phase aims to minimize the total message volume that will be incurred due to the replication/migration of input data while maintaining balance on computational and receive-volume loads of processors. The network-flow-based model proposed for the second phase aims to minimize the maximum message volume handled by processors via utilizing the flexibility in assigning send-communication tasks to processors, which is introduced by data replication. The validity of our proposed model is verified on parallelization of a direct volume rendering algorithm.

Cite as

Cevdet Aykanat, Erkan Okuyan, and B. Barla Cambazoglu. A Model for Task Repartioning under Data Replication. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{aykanat_et_al:DagSemProc.09061.2,
  author =	{Aykanat, Cevdet and Okuyan, Erkan and Cambazoglu, B. Barla},
  title =	{{A Model for Task Repartioning under Data Replication}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.2},
  URN =		{urn:nbn:de:0030-drops-20903},
  doi =		{10.4230/DagSemProc.09061.2},
  annote =	{Keywords: Task repartitioning, data replication, hypergraph partitioning with fixed vertices, assignment flow network}
}
Document
A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix

Authors: Samuel I. Daitch and Daniel A. Spielman

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
We present an algorithm for solving a linear system in a symmetric M-matrix. In particular, for $n times n$ symmetric M-matrix $M$, we show how to find a diagonal matrix $D$ such that $DMD$ is diagonally-dominant. To compute $D$, the algorithm must solve $O{log n}$ linear systems in diagonally-dominant matrices. If we solve these diagonally-dominant systems approximately using the Spielman-Teng nearly-linear time solver, then we obtain an algorithm for approximately solving linear systems in symmetric M-matrices, for which the expected running time is also nearly-linear.

Cite as

Samuel I. Daitch and Daniel A. Spielman. A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{daitch_et_al:DagSemProc.09061.3,
  author =	{Daitch, Samuel I. and Spielman, Daniel A.},
  title =	{{A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.3},
  URN =		{urn:nbn:de:0030-drops-20803},
  doi =		{10.4230/DagSemProc.09061.3},
  annote =	{Keywords: M-matrix, diagonally-dominant matrix, linear system solver, iterative algorithm, randomized algorithm, network flow, gain graph}
}
Document
Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO)

Authors: Jan Riehme and Andreas Griewank

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO) is based on the principle of Instant Elimination: At runtime we dynamically maintain a DAG representing only active variables that are alive at any time. Whenever an active variable is deallocated or its value is overwritten the corresponding vertex in the Live-DAG will be eliminated immediately by the well known vertex elimination rule [1]. Consequently, the total memory requirement is equal to that of the sparse forward mode. Assuming that local variables are destructed in the opposite order of their construction (as in C++), a single assignment code is in effect differentiated in reverse mode. If compiler-generated temporaries are destroyed in reverse order too, then Instant Elimination yields the statement level reverse mode of ADIFOR [2] naturally. The user determines the elimination order intentionally (or unintentionally) by the order in which he declares variables, which makes hybrid modes of AD possible by combining forward and reverse differentiated parts. By annotating the Live-DAG with local Hessians and applying second order elimination rules, Hessian-vector products can be computed efficiently since the annotated Live-DAG stores one half of the symmetric Hessian graph only (as suggested in [1]). Nested automatic differentiation is done easily by subsequent propagations, since sensitivities between variables alive can be obtained at any point in time within the Live-DAG. The concept of maintaining a Live-DAG fits optimally into the strategy of overloaded operators for classes, it is a very natural example of Object Oriented Programming. A proof-of-concept implementation in C++ is available (contact the first author). References 1. Griewank, A.: Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation. SIAM (2000) 2.Bischof, C.H., Carle, A., Khademi, P., Mauer, A.: ADIFOR 2.0: Automatic differentiation of Fortran 77 programs. IEEE Computational Science & Engineering 3 (1996) 18-32

Cite as

Jan Riehme and Andreas Griewank. Algorithmic Differentiation Through Automatic Graph Elimination Ordering (ADTAGEO). In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{riehme_et_al:DagSemProc.09061.4,
  author =	{Riehme, Jan and Griewank, Andreas},
  title =	{{Algorithmic Differentiation Through Automatic Graph  Elimination Ordering (ADTAGEO)}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.4},
  URN =		{urn:nbn:de:0030-drops-20852},
  doi =		{10.4230/DagSemProc.09061.4},
  annote =	{Keywords: Automatic Differentiation, Instant Elimination, Live-DAG, symmetric Hessian-DAG, forward mode, reverse mode, checkpointing, ADTAGEO}
}
Document
Combinatorial Problems in High-Performance Computing: Partitioning

Authors: Rob Bisseling, Tristan van Leeuwen, and Umit V. Catalyurek

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
This extended abstract presents a survey of combinatorial problems encountered in scientific computations on today's high-performance architectures, with sophisticated memory hierarchies, multiple levels of cache, and multiple processors on chip as well as off-chip. For parallelism, the most important problem is to partition sparse matrices, graph, or hypergraphs into nearly equal-sized parts while trying to reduce inter-processor communication. Common approaches to such problems involve multilevel methods based on coarsening and uncoarsening (hyper)graphs, matching of similar vertices, searching for good separator sets and good splittings, dynamical adjustment of load imbalance, and two-dimensional matrix splitting methods.

Cite as

Rob Bisseling, Tristan van Leeuwen, and Umit V. Catalyurek. Combinatorial Problems in High-Performance Computing: Partitioning. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{bisseling_et_al:DagSemProc.09061.6,
  author =	{Bisseling, Rob and van Leeuwen, Tristan and Catalyurek, Umit V.},
  title =	{{Combinatorial Problems in High-Performance Computing: Partitioning}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.6},
  URN =		{urn:nbn:de:0030-drops-20818},
  doi =		{10.4230/DagSemProc.09061.6},
  annote =	{Keywords: Partitioning, sparse matrix, hypergraph, parallel, HPC}
}
Document
Combinatorial Problems in OpenAD

Authors: Jean Utke and Uwe Naumann

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
Computing derivatives using automatic differentiation methods entails a variety of combinatorial problems. The OpenAD tool implements automatic differentiation as source transformation of a program that represents a numerical model. We select three combinatorial problems and discuss the solutions implemented in OpenAD. Our intention is to explain the specific parts of the implementation so that readers can easily use OpenAD to investigate and develop their own solutions to these problems.

Cite as

Jean Utke and Uwe Naumann. Combinatorial Problems in OpenAD. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{utke_et_al:DagSemProc.09061.7,
  author =	{Utke, Jean and Naumann, Uwe},
  title =	{{Combinatorial Problems in OpenAD}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.7},
  URN =		{urn:nbn:de:0030-drops-20954},
  doi =		{10.4230/DagSemProc.09061.7},
  annote =	{Keywords: Automatic differentiation, combinatorial problem, tool tutorial}
}
Document
Combinatorial problems in solving linear systems

Authors: Iain S. Duff and Bora Ucar

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
Numerical linear algebra and combinatorial optimization are vast subjects; as is their interaction. In virtually all cases there should be a notion of sparsity for a combinatorial problem to arise. Sparse matrices, therefore, form the basis of the interaction of these two seemingly disparate subjects. As the core of many of today's numerical linear algebra computations consists of sparse linear system solutions, we will cover combinatorial problems, notions, and algorithms relating to those computations. This talk is thus concerned with direct and iterative methods for sparse linear systems and their intercation with combinatorial optimization. On the direct methods side, we discuss matrix ordering; bipartite matching and matrix scaling for better pivoting; task assignment and scheduling for parallel multifrontal solvers. On the iterative method side, we discuss preconditioning techniques including incomplete factor preconditioners (notion of level of fill-in), support graph preconditioners (graph embedding concepts), and algebraic multigrids (independent sets in undirected graphs). In a separate part of the talk, we discuss methods that aim to exploit sparsity during linear system solution. These methods include block diagonalization of the matrix; efficient triangular system solutions for right-hand side vectors of single nonzero entries. Towards the end, we mention, quite briefly as they are topics of other invited talks, some other areas whose interactions with combinatorial optimization are of great benefit to numerical linear algebra. These include graph and hypergraph partitioning for load balancing problems, and colouring problems in numerical optimization. On closing, we compile and list a set of open problems.

Cite as

Iain S. Duff and Bora Ucar. Combinatorial problems in solving linear systems. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{duff_et_al:DagSemProc.09061.8,
  author =	{Duff, Iain S. and Ucar, Bora},
  title =	{{Combinatorial problems in solving linear systems}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--37},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.8},
  URN =		{urn:nbn:de:0030-drops-20779},
  doi =		{10.4230/DagSemProc.09061.8},
  annote =	{Keywords: Combinatorial scientific computing, graph theory, combinatorial optimization, sparse matrices, linear system solution}
}
Document
Distillating knowledge about SCOTCH

Authors: Francois Pellegrini

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
The design of the Scotch library for static mapping, graph partitioning and sparse matrix ordering is highly modular, so as to allow users and potential contributors to tweak it and add easily new static mapping, graph bipartitioning, vertex separation or graph ordering methods to match their particular needs. The purpose of this tutorial is twofold. It will start with a description of the interface of Scotch, presenting its visible objects and data structures. Then, we will step into the API mirror and have a look at the inside: the internal representation of graphs, mappings and orderings, and the basic sequential and parallel building blocks: graph induction, graph coarsening which can be re-used by third-party software. As an example, we will show how to add a simple genetic algorithm routine to the graph bipartitioning methods.

Cite as

Francois Pellegrini. Distillating knowledge about SCOTCH. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{pellegrini:DagSemProc.09061.9,
  author =	{Pellegrini, Francois},
  title =	{{Distillating knowledge about SCOTCH}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.9},
  URN =		{urn:nbn:de:0030-drops-20914},
  doi =		{10.4230/DagSemProc.09061.9},
  annote =	{Keywords: Scotch, graph algorithms, data structures}
}
Document
Getting Started with ADOL-C

Authors: Andrea Walther

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
The C++ package ADOL-C described in this paper facilitates the evaluation of first and higher derivatives of vector functions that are defined by computer programs written in C or C++. The numerical values of derivative vectors are obtained free of truncation errors at mostly a small multiple of the run time and a fix small multiple random access memory required by the given function evaluation program. Derivative matrices are obtained by columns, by rows or in sparse format. This tutorial describes the source code modification required for the application of ADOL-C, the most frequently used drivers to evaluate derivatives and some recent developments.

Cite as

Andrea Walther. Getting Started with ADOL-C. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{walther:DagSemProc.09061.10,
  author =	{Walther, Andrea},
  title =	{{Getting Started with ADOL-C}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.10},
  URN =		{urn:nbn:de:0030-drops-20849},
  doi =		{10.4230/DagSemProc.09061.10},
  annote =	{Keywords: ADOL-C, algorithmic differentiation of C/C++ programs}
}
Document
Getting Started with Zoltan: A Short Tutorial

Authors: Karen D. Devine, Erik G. Boman, Lee Ann Riesen, Umit V. Catalyurek, and Cédric Chevalier

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
The Zoltan library is a toolkit of parallel combinatorial algorithms for unstructured and/or adaptive computations. In this paper, we briefly describe the most significant tools in Zoltan: dynamic partitioning, graph coloring and ordering. We also describe how to obtain, build, and use Zoltan in parallel applications.

Cite as

Karen D. Devine, Erik G. Boman, Lee Ann Riesen, Umit V. Catalyurek, and Cédric Chevalier. Getting Started with Zoltan: A Short Tutorial. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{devine_et_al:DagSemProc.09061.11,
  author =	{Devine, Karen D. and Boman, Erik G. and Riesen, Lee Ann and Catalyurek, Umit V. and Chevalier, C\'{e}dric},
  title =	{{Getting Started with Zoltan: A Short Tutorial}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.11},
  URN =		{urn:nbn:de:0030-drops-20886},
  doi =		{10.4230/DagSemProc.09061.11},
  annote =	{Keywords: Parallel computing, load balancing, partitioning, coloring, ordering, software}
}
Document
Low-Memory Tour Reversal in Directed Graphs

Authors: Viktor Mosenkis, Uwe Naumann, and Elmar Peise

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
We consider the problem of reversing a {em tour} $(i_1,i_2,ldots,i_l)$ in a directed graph $G=(V,E)$ with positive integer vertices $V$ and edges $E subseteq V imes V$, where $i_j in V$ and $(i_j,i_{j+1}) in E$ for all $j=1,ldots,l-1.$ The tour can be processed in last-in-first-out order as long as the size of the corresponding stack does not exceed the available memory. This constraint is violated in most cases when considering control-flow graphs of large-scale numerical simulation programs. The tour reversal problem also arises in adjoint programs used, for example, in the context of derivative-based nonlinear optimization, sensitivity analysis, or other, often inverse, problems. The intention is to compress the tour in order not to run out of memory. As the general optimal compression problem was proven to be NP-hard and big control-flow graphs results from loops in programs we do not want to use general purpose algorithms to compress the tour. We want rather to compress the tour by finding loops and replace the redundant information by proper representation of the loops.

Cite as

Viktor Mosenkis, Uwe Naumann, and Elmar Peise. Low-Memory Tour Reversal in Directed Graphs. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{mosenkis_et_al:DagSemProc.09061.12,
  author =	{Mosenkis, Viktor and Naumann, Uwe and Peise, Elmar},
  title =	{{Low-Memory Tour Reversal in Directed Graphs}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.12},
  URN =		{urn:nbn:de:0030-drops-20924},
  doi =		{10.4230/DagSemProc.09061.12},
  annote =	{Keywords: Directed graph, tour reversal, offline algorithm, dynamic programming, online algorithm, control-flow reversal, adjoint program}
}
Document
Multifrontral multithreaded rank-revealing sparse QR factorization

Authors: Timothy Davis

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
SuiteSparseQR is a sparse multifrontal QR factorization algorithm. Dense matrix methods within each frontal matrix enable the method to obtain high performance on multicore architectures. Parallelism across different frontal matrices is handled with Intel's Threading Building Blocks library. Rank-detection is performed within each frontal matrix using Heath's method, which does not require column pivoting. The resulting sparse QR factorization obtains a substantial fraction of the theoretical peak performance of a multicore computer.

Cite as

Timothy Davis. Multifrontral multithreaded rank-revealing sparse QR factorization. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{davis:DagSemProc.09061.13,
  author =	{Davis, Timothy},
  title =	{{Multifrontral multithreaded rank-revealing sparse QR factorization}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.13},
  URN =		{urn:nbn:de:0030-drops-20781},
  doi =		{10.4230/DagSemProc.09061.13},
  annote =	{Keywords: Sparse matrix algorithms, QR factorization, multifrontal}
}
Document
Randomized Heuristics for Exploiting Jacobian Scarcity

Authors: Andrew Lyons and Ilya Safro

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)


Abstract
Griewank and Vogel introduced the notion of Jacobian scarcity, which generalizes the properties of sparsity and rank to capture a kind of deficiency in the degrees of freedom of the Jacobian matrix $F'(mathbf{x}).$ We describe new randomized heuristics that exploit scarcity for the optimized evaluation of collections of Jacobian-vector or Jacobian-transpose-vector products.

Cite as

Andrew Lyons and Ilya Safro. Randomized Heuristics for Exploiting Jacobian Scarcity. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{lyons_et_al:DagSemProc.09061.15,
  author =	{Lyons, Andrew and Safro, Ilya},
  title =	{{Randomized Heuristics for Exploiting Jacobian Scarcity}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.15},
  URN =		{urn:nbn:de:0030-drops-20868},
  doi =		{10.4230/DagSemProc.09061.15},
  annote =	{Keywords: Jacobian, scarcity, accumulation, directed acyclic graph}
}
  • Refine by Author
  • 3 Catalyurek, Umit V.
  • 3 Naumann, Uwe
  • 2 Chevalier, Cédric
  • 2 Safro, Ilya
  • 1 Aykanat, Cevdet
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 ADOL-C
  • 1 ADTAGEO
  • 1 Algebraic multigrid
  • 1 Automatic Differentiation
  • 1 Automatic differentiation
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 21 2009

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail