2 Search Results for "O’Leary, Dianne P."

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.131
Deterministic Complexity Analysis of Hermitian Eigenproblems

Authors: Aleksandros Sobczyk

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix A can be diagonalized with a randomized algorithm in O(n^{ω}log²(n/ε)) arithmetic operations, where ω≲ 2.371 is the square matrix multiplication exponent, and [Shah, SODA 2025] significantly improved the bit complexity for the Hermitian case. Our main goal is to obtain similar deterministic complexity bounds for various Hermitian eigenproblems. In the Real RAM model, we show that a Hermitian matrix can be diagonalized deterministically in O(n^{ω}log(n)+n²polylog(n/ε)) arithmetic operations, improving the classic deterministic Õ(n³) algorithms, and derandomizing the aforementioned state-of-the-art. The main technical step is a complete, detailed analysis of a well-known divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95], when accelerated with the Fast Multipole Method, asserting that it can accurately diagonalize a symmetric tridiagonal matrix in nearly-O(n²) operations. In finite precision, we show that an algorithm by Schönhage [Sch72] to reduce a Hermitian matrix to tridiagonal form is stable in the floating point model, using O(log(n/ε)) bits of precision. This leads to a deterministic algorithm to compute all the eigenvalues of a Hermitian matrix in O(n^{ω}ℱ(log(n/ε)) + n²polylog(n/ε)) bit operations, where ℱ(b) ∈ Õ(b) is the bit complexity of a single floating point operation on b bits. This improves the best known Õ(n³) deterministic and O(n^{ω}log²(n/ε)ℱ(log(n/ε))) randomized complexities. We conclude with some other useful subroutines such as computing spectral gaps, condition numbers, and spectral projectors, and with some open problems.
Cite as

Aleksandros Sobczyk. Deterministic Complexity Analysis of Hermitian Eigenproblems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 131:1-131:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sobczyk:LIPIcs.ICALP.2025.131,
  author =	{Sobczyk, Aleksandros},
  title =	{{Deterministic Complexity Analysis of Hermitian Eigenproblems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{131:1--131:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.131},
  URN =		{urn:nbn:de:0030-drops-235081},
  doi =		{10.4230/LIPIcs.ICALP.2025.131},
  annote =	{Keywords: Hermitian eigenproblem, eigenvalues, SVD, tridiagonal reduction, matrix multiplication time, diagonalization, bit complexity}
}
Document
DOI: 10.4230/DFU.Vol2.SciViz.2011.160
Salient Frame Detection for Molecular Dynamics Simulations

Authors: Youngmin Kim, Robert Patro, Cheuk Yiu Ip, Dianne P. O’Leary, and Andriy Anishkin

Published in: Dagstuhl Follow-Ups, Volume 2, Scientific Visualization: Interactions, Features, Metaphors (2011)

Abstract
Recent advances in sophisticated computational techniques have facilitated simulation of incrediblydetailed time-varying trajectories and in the process have generated vast quantities of simulation data. The current tools to analyze and comprehend large-scale time-varying data, however, lag far behind our ability to produce such simulation data. Saliency-based analysis can be applied to time-varying 3D datasets for the purpose of summarization, abstraction, and motion analysis. As the sizes of time-varying datasets continue to grow, it becomes more and more difficult to comprehend vast amounts of data and information in a short period of time. In this paper, we use eigenanalysis to generate orthogonal basis functions over sliding windows to characterize regions of unusual deviations and significant trends. Our results show that motion subspaces provide an effective technique for summarization of large molecular dynamics trajectories.
Cite as

Youngmin Kim, Robert Patro, Cheuk Yiu Ip, Dianne P. O’Leary, and Andriy Anishkin. Salient Frame Detection for Molecular Dynamics Simulations. In Scientific Visualization: Interactions, Features, Metaphors. Dagstuhl Follow-Ups, Volume 2, pp. 160-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InCollection{kim_et_al:DFU.Vol2.SciViz.2011.160,
  author =	{Kim, Youngmin and Patro, Robert and Yiu Ip, Cheuk and O’Leary, Dianne P. and Anishkin, Andriy},
  title =	{{Salient Frame Detection for Molecular Dynamics Simulations}},
  booktitle =	{Scientific Visualization: Interactions, Features, Metaphors},
  pages =	{160--175},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-26-2},
  ISSN =	{1868-8977},
  year =	{2011},
  volume =	{2},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol2.SciViz.2011.160},
  URN =		{urn:nbn:de:0030-drops-32926},
  doi =		{10.4230/DFU.Vol2.SciViz.2011.160},
  annote =	{Keywords: Saliency based analysis, Molecular Dynamics, Simulation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2011

  • Refine by Author
  • 1 Anishkin, Andriy
  • 1 Kim, Youngmin
  • 1 O’Leary, Dianne P.
  • 1 Patro, Robert
  • 1 Sobczyk, Aleksandros
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DFU

  • Refine by Classification
  • 1 Theory of computation → Divide and conquer
  • 1 Theory of computation → Numeric approximation algorithms

  • Refine by Keyword
  • 1 Hermitian eigenproblem
  • 1 Molecular Dynamics
  • 1 SVD
  • 1 Saliency based analysis
  • 1 Simulation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact