5 Search Results for "Püschel, Markus"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.33
Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

Authors: Sílvia Casacuberta and Rasmus Kyng

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We improve the current best running time value to invert sparse matrices over finite fields, lowering it to an expected O(n^{2.2131}) time for the current values of fast rectangular matrix multiplication. We achieve the same running time for the computation of the rank and nullspace of a sparse matrix over a finite field. This improvement relies on two key techniques. First, we adopt the decomposition of an arbitrary matrix into block Krylov and Hankel matrices from Eberly et al. (ISSAC 2007). Second, we show how to recover the explicit inverse of a block Hankel matrix using low displacement rank techniques for structured matrices and fast rectangular matrix multiplication algorithms. We generalize our inversion method to block structured matrices with other displacement operators and strengthen the best known upper bounds for explicit inversion of block Toeplitz-like and block Hankel-like matrices, as well as for explicit inversion of block Vandermonde-like matrices with structured blocks. As a further application, we improve the complexity of several algorithms in topological data analysis and in finite group theory.
Cite as

Sílvia Casacuberta and Rasmus Kyng. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 33:1-33:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{casacuberta_et_al:LIPIcs.ITCS.2022.33,
  author =	{Casacuberta, S{\'\i}lvia and Kyng, Rasmus},
  title =	{{Faster Sparse Matrix Inversion and Rank Computation in Finite Fields}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{33:1--33:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.33},
  URN =		{urn:nbn:de:0030-drops-156290},
  doi =		{10.4230/LIPIcs.ITCS.2022.33},
  annote =	{Keywords: Matrix inversion, rank computation, displacement operators, numerical linear algebra}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2015.238
Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems

Authors: Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Arvind K. Sujeeth, Manohar Jonnalagedda, Nada Amin, Georg Ofenbeck, Alen Stojanov, Yannis Klonatos, Mohammad Dashti, Christoph Koch, Markus Püschel, and Kunle Olukotun

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)

Abstract
Most performance critical software is developed using very low-level techniques. We argue that this needs to change, and that generative programming is an effective avenue to enable the use of high-level languages and programming techniques in many such circumstances.
Cite as

Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Arvind K. Sujeeth, Manohar Jonnalagedda, Nada Amin, Georg Ofenbeck, Alen Stojanov, Yannis Klonatos, Mohammad Dashti, Christoph Koch, Markus Püschel, and Kunle Olukotun. Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 238-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{rompf_et_al:LIPIcs.SNAPL.2015.238,
  author =	{Rompf, Tiark and Brown, Kevin J. and Lee, HyoukJoong and Sujeeth, Arvind K. and Jonnalagedda, Manohar and Amin, Nada and Ofenbeck, Georg and Stojanov, Alen and Klonatos, Yannis and Dashti, Mohammad and Koch, Christoph and P\"{u}schel, Markus and Olukotun, Kunle},
  title =	{{Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{238--261},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.238},
  URN =		{urn:nbn:de:0030-drops-50295},
  doi =		{10.4230/LIPIcs.SNAPL.2015.238},
  annote =	{Keywords: Performance, Generative Programming, Staging, DSLs}
}
Document
DOI: 10.4230/DagSemProc.10191.1
10191 Abstracts Collection – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond

Authors: Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel

Published in: Dagstuhl Seminar Proceedings, Volume 10191, Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond (2010)

Abstract
From May 9 to 12, 2010, the Dagstuhl Seminar 10191 ``Program Composition and Optimization: Autotuning, Scheduling, Metaprogramming and Beyond'' 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

Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel. 10191 Abstracts Collection – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond. In Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond. Dagstuhl Seminar Proceedings, Volume 10191, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kessler_et_al:DagSemProc.10191.1,
  author =	{Kessler, Christoph W. and L\"{o}we, Welf and Padua, David and P\"{u}schel, Markus},
  title =	{{10191 Abstracts Collection – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond}},
  booktitle =	{Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10191},
  editor =	{Christoph W. Kessler and Welf L\"{o}we and David Padua and Markus P\"{u}schel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10191.1},
  URN =		{urn:nbn:de:0030-drops-25726},
  doi =		{10.4230/DagSemProc.10191.1},
  annote =	{Keywords: Software composition, program optimization, components, parallel computing, scheduling, autotuning, adaptivity, performance prediction, library synthesis, meta-programming}
}
Document
DOI: 10.4230/DagSemProc.10191.2
10191 Executive Summary – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond

Authors: Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel

Published in: Dagstuhl Seminar Proceedings, Volume 10191, Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond (2010)

Abstract
Components are a well-proven means of handling software complexity. Reusable components and software composition support the construction of large and reliable software systems from pre-defined and tested partial solutions. When maximizing reusability, we end up with components that are very general and do not fit one particular scenario perfectly. Therefore, adaptation, especially optimization, is established as a technique to deal with such mismatches.
Cite as

Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel. 10191 Executive Summary – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond. In Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond. Dagstuhl Seminar Proceedings, Volume 10191, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kessler_et_al:DagSemProc.10191.2,
  author =	{Kessler, Christoph W. and L\"{o}we, Welf and Padua, David and P\"{u}schel, Markus},
  title =	{{10191 Executive Summary – Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond}},
  booktitle =	{Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10191},
  editor =	{Christoph W. Kessler and Welf L\"{o}we and David Padua and Markus P\"{u}schel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10191.2},
  URN =		{urn:nbn:de:0030-drops-25712},
  doi =		{10.4230/DagSemProc.10191.2},
  annote =	{Keywords: Software composition, program optimization, components, parallel computing, scheduling, autotuning, adaptivity, performance prediction, library synthesis, meta-programming}
}
Document
DOI: 10.4230/DagSemProc.10191.3
Program Composition and Optimization: An Introduction

Authors: Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel

Published in: Dagstuhl Seminar Proceedings, Volume 10191, Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond (2010)

Abstract
Software composition connects separately defined software artifacts. Such connection may be in program structure (such as inheritance), data flow (such as message passing) and/or control flow (such as function calls or loop control).
Cite as

Christoph W. Kessler, Welf Löwe, David Padua, and Markus Püschel. Program Composition and Optimization: An Introduction. In Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond. Dagstuhl Seminar Proceedings, Volume 10191, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kessler_et_al:DagSemProc.10191.3,
  author =	{Kessler, Christoph W. and L\"{o}we, Welf and Padua, David and P\"{u}schel, Markus},
  title =	{{Program Composition and Optimization: An Introduction}},
  booktitle =	{Program Composition and Optimization : Autotuning, Scheduling, Metaprogramming and Beyond},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10191},
  editor =	{Christoph W. Kessler and Welf L\"{o}we and David Padua and Markus P\"{u}schel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10191.3},
  URN =		{urn:nbn:de:0030-drops-25738},
  doi =		{10.4230/DagSemProc.10191.3},
  annote =	{Keywords: Software composition, program optimization, components, parallel computing, scheduling, autotuning, adaptivity, performance prediction, library synthesis, meta-programming}
}
  • Refine by Author
  • 4 Püschel, Markus
  • 3 Kessler, Christoph W.
  • 3 Löwe, Welf
  • 3 Padua, David
  • 1 Amin, Nada
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 3 Software composition
  • 3 adaptivity
  • 3 autotuning
  • 3 components
  • 3 library synthesis
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2010
  • 1 2015
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact