Search Results

Documents authored by Giesen, Joachim

Document
DOI: 10.4230/LIPIcs.SEA.2024.27
Improved Cut Strategy for Tensor Network Contraction Orders

Authors: Christoph Staudt, Mark Blacher, Julien Klaus, Farin Lippmann, and Joachim Giesen

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
In the field of quantum computing, simulating quantum systems on classical computers is crucial. Tensor networks are fundamental in simulating quantum systems. A tensor network is a collection of tensors, that need to be contracted into a result tensor. Tensor contraction is a generalization of matrix multiplication to higher order tensors. The contractions can be performed in different orders, and the order has a significant impact on the number of floating point operations (flops) needed to get the result tensor. It is known that finding an optimal contraction order is NP-hard. The current state-of-the-art approach for finding efficient contraction orders is to combinine graph partitioning with a greedy strategy. Although heavily used in practice, the current approach ignores so-called free indices, chooses node weights without regarding previous computations, and requires numerous hyperparameters that need to be tuned at runtime. In this paper, we address these shortcomings by developing a novel graph cut strategy. The proposed modifications yield contraction orders that significantly reduce the number of flops in the tensor contractions compared to the current state of the art. Moreover, by removing the need for hyperparameter tuning at runtime, our approach converges to an efficient solution faster, which reduces the required optimization time by at least an order of magnitude.
Cite as

Christoph Staudt, Mark Blacher, Julien Klaus, Farin Lippmann, and Joachim Giesen. Improved Cut Strategy for Tensor Network Contraction Orders. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{staudt_et_al:LIPIcs.SEA.2024.27,
  author =	{Staudt, Christoph and Blacher, Mark and Klaus, Julien and Lippmann, Farin and Giesen, Joachim},
  title =	{{Improved Cut Strategy for Tensor Network Contraction Orders}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.27},
  URN =		{urn:nbn:de:0030-drops-203924},
  doi =		{10.4230/LIPIcs.SEA.2024.27},
  annote =	{Keywords: tensor network, contraction order, graph partitioniong, quantum simulation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.3
Fast and Robust Vectorized In-Place Sorting of Primitive Types

Authors: Mark Blacher, Joachim Giesen, and Lars Kühne

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Modern CPUs provide single instruction-multiple data (SIMD) instructions. SIMD instructions process several elements of a primitive data type simultaneously in fixed-size vectors. Classical sorting algorithms are not directly expressible in SIMD instructions. Accelerating sorting algorithms with SIMD instruction is therefore a creative endeavor. A promising approach for sorting with SIMD instructions is to use sorting networks for small arrays and Quicksort for large arrays. In this paper we improve vectorization techniques for sorting networks and Quicksort. In particular, we show how to use the full capacity of vector registers in sorting networks and how to make vectorized Quicksort robust with respect to different key distributions. To demonstrate the performance of our techniques we implement an in-place hybrid sorting algorithm for the data type int with AVX2 intrinsics. Our implementation is at least 30% faster than state-of-the-art high-performance sorting alternatives.
Cite as

Mark Blacher, Joachim Giesen, and Lars Kühne. Fast and Robust Vectorized In-Place Sorting of Primitive Types. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blacher_et_al:LIPIcs.SEA.2021.3,
  author =	{Blacher, Mark and Giesen, Joachim and K\"{u}hne, Lars},
  title =	{{Fast and Robust Vectorized In-Place Sorting of Primitive Types}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.3},
  URN =		{urn:nbn:de:0030-drops-137758},
  doi =		{10.4230/LIPIcs.SEA.2021.3},
  annote =	{Keywords: Quicksort, Sorting Networks, Vectorization, SIMD, AVX2}
}
Document
DOI: 10.4230/DagRep.3.6.67
Parallel Data Analysis (Dagstuhl Seminar 13251)

Authors: Artur Andrzejak, Joachim Giesen, Raghu Ramakrishnan, and Ion Stoica

Published in: Dagstuhl Reports, Volume 3, Issue 6 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13251 "Parallel Data Analysis" which was held in Schloss Dagstuhl - Leibniz Center for Informatics from June 16th 2013 to June 21st 2013. During the seminar, participants presented their current research and ongoing work, and open problems were discussed. The first part of this document describes seminar goals and topics, while the remainder gives an overview of the contents discussed during this event. Abstracts of a subset of the presentations given during the seminar are put together in this paper. Links to extended abstracts or full papers are provided, if available.
Cite as

Artur Andrzejak, Joachim Giesen, Raghu Ramakrishnan, and Ion Stoica. Parallel Data Analysis (Dagstuhl Seminar 13251). In Dagstuhl Reports, Volume 3, Issue 6, pp. 67-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{andrzejak_et_al:DagRep.3.6.67,
  author =	{Andrzejak, Artur and Giesen, Joachim and Ramakrishnan, Raghu and Stoica, Ion},
  title =	{{Parallel Data Analysis (Dagstuhl Seminar 13251)}},
  pages =	{67--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{6},
  editor =	{Andrzejak, Artur and Giesen, Joachim and Ramakrishnan, Raghu and Stoica, Ion},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.6.67},
  URN =		{urn:nbn:de:0030-drops-42580},
  doi =		{10.4230/DagRep.3.6.67},
  annote =	{Keywords: data analysis, machine learning, parallel processing, distributed computing, software frameworks}
}
Document
DOI: 10.4230/DagSemProc.09111.3
Minimizing Absolute Gaussian Curvature Locally

Authors: Joachim Giesen and Manjunath Madhusudan

Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)

Abstract
One of the remaining challenges when reconstructing a surface from a finite sample is recovering non-smooth surface features like sharp edges. There is practical evidence showing that a two step approach could be an aid to this problem, namely, first computing a polyhedral reconstruction isotopic to the sampled surface, and secondly minimizing the absolute Gaussian curvature of this reconstruction globally. The first step ensures topological correctness and the second step improves the geometric accuracy of the reconstruction in the presence of sharp features without changing its topology. Unfortunately it is computationally hard to minimize the absolute Gaussian curvature globally. Hence we study a local variant of absolute Gaussian curvature minimization problem which is still meaningful in the context of surface fairing. Absolute Gaussian curvature like Gaussian curvature is concentrated at the vertices of a polyhedral surface embedded into $mathbb{R}^3$. Local optimization tries to move a single vertex in space such that the absolute Gaussian curvature at this vertex is minimized. We show that in general it is algebraically hard to find the optimal position of a vertex. By algebraically hard we mean that in general an optimal solution is not constructible, i.e., there exist no finite sequence of expressions starting with rational numbers, where each expression is either the sum, difference, product, quotient or $k$'th root of preceding expressions and the last expressions give the coordinates of an optimal solution. Hence the only option left is to approximate the optimal position. We provide an approximation scheme for the minimum possible value of the absolute Gaussian curvature at a vertex.
Cite as

Joachim Giesen and Manjunath Madhusudan. Minimizing Absolute Gaussian Curvature Locally. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{giesen_et_al:DagSemProc.09111.3,
  author =	{Giesen, Joachim and Madhusudan, Manjunath},
  title =	{{Minimizing Absolute Gaussian Curvature Locally}},
  booktitle =	{Computational Geometry},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9111},
  editor =	{Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.3},
  URN =		{urn:nbn:de:0030-drops-20311},
  doi =		{10.4230/DagSemProc.09111.3},
  annote =	{Keywords: Absolute Gaussian curvature, surface reconstruction, mesh smoothing}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact