25 Search Results for "Kaltofen, Erich"

Document
DOI: 10.4230/LIPIcs.STACS.2026.70
A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Authors: Priyanshu Pant, Surabhi Chakrabartty, and Ranveer Singh

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The rank of an n × n matrix A is equal to the maximum order of a square submatrix with a nonzero determinant; it can be computed in O(n^{2.37}) time. Analogously, the maximum order of a square submatrix with nonzero permanent is defined as the permanental rank ρ_{per}(A). Computing the permanent or the coefficients of the permanental polynomial per(xI-A) is #P-complete. The permanental nullity η_{per}(A) is defined as the multiplicity of zero as a root of the permanental polynomial. We establish a permanental analog of the rank–nullity theorem, ρ_{per}(A) + η_{per}(A) = n for symmetric nonnegative matrices, positive semidefinite matrices, and adjacency matrices of balanced signed graphs. Using this theorem, we can compute the permanental nullity for these classes in polynomial time. For {0,± 1}-matrices, we also provide a complete characterization of when the permanental rank-nullity identity holds.
Cite as

Priyanshu Pant, Surabhi Chakrabartty, and Ranveer Singh. A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 70:1-70:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pant_et_al:LIPIcs.STACS.2026.70,
  author =	{Pant, Priyanshu and Chakrabartty, Surabhi and Singh, Ranveer},
  title =	{{A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{70:1--70:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.70},
  URN =		{urn:nbn:de:0030-drops-255590},
  doi =		{10.4230/LIPIcs.STACS.2026.70},
  annote =	{Keywords: permanent, matrix rank, #P-completeness, graph algorithms, permanental polynomial, spectral graph theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.49
Debordering Closure Results in Determinantal and Pfaffian Ideals

Authors: Anakin Dey and Zeyu Guo

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
One important question in algebraic complexity is understanding the complexity of polynomial ideals (Grochow, Bulletin of EATCS 131, 2020). Andrews and Forbes (STOC 2022) studied the determinantal ideals I^{det}_{n,m,r} generated by the r× r minors of n× m matrices. Over fields of characteristic zero or of sufficiently large characteristic, they showed that for any nonzero f ∈ I^{det}_{n,m,r}, the determinant of a t × t matrix of variables with t = Θ{r^{1/3}} is approximately computed by a constant-depth, polynomial-size f-oracle algebraic circuit, in the sense that the determinant lies in the border of such circuits. An analogous result was also obtained for Pfaffians in the same paper. In this work, we deborder the result of Andrews and Forbes by showing that when f has polynomial degree, the determinant is in fact exactly computed by a constant-depth, polynomial-size f-oracle algebraic circuit. We further establish an analogous result for Pfaffian ideals. Our results are established using the isolation lemma, combined with a careful analysis of straightening-law expansions of polynomials in determinantal and Pfaffian ideals.
Cite as

Anakin Dey and Zeyu Guo. Debordering Closure Results in Determinantal and Pfaffian Ideals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ITCS.2026.49,
  author =	{Dey, Anakin and Guo, Zeyu},
  title =	{{Debordering Closure Results in Determinantal and Pfaffian Ideals}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.49},
  URN =		{urn:nbn:de:0030-drops-253363},
  doi =		{10.4230/LIPIcs.ITCS.2026.49},
  annote =	{Keywords: Algebraic circuit complexity, Isolation lemma, Debordering}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.9
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Authors: Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.
Cite as

Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andrews_et_al:LIPIcs.ITCS.2026.9,
  author =	{Andrews, Robert and Armand, Jules and Dwivedi, Prateek and Hansen, Magnus Rahbek Dalgaard and Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On Closure Properties of Read-Once Oblivious Algebraic Branching Programs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.9},
  URN =		{urn:nbn:de:0030-drops-252964},
  doi =		{10.4230/LIPIcs.ITCS.2026.9},
  annote =	{Keywords: Factoring, Closure Properties, Sparsity Bounds, Symmetric Polynomials, roABP, Expander Graphs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.15
Algebraic Pseudorandomness in VNC⁰

Authors: Robert Andrews

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study the arithmetic complexity of hitting set generators, which are pseudorandom objects used for derandomization of the polynomial identity testing problem. We give new explicit constructions of hitting set generators whose outputs are computable in VNC⁰, i.e., can be computed by arithmetic formulas of constant size. Unconditionally, we construct a VNC⁰-computable generator that hits arithmetic circuits of constant depth and polynomial size. We also give conditional constructions, under strong but plausible hardness assumptions, of VNC⁰-computable generators that hit arithmetic formulas and arithmetic branching programs of polynomial size, respectively. As a corollary of our constructions, we derive lower bounds for subsystems of the Geometric Ideal Proof System of Grochow and Pitassi. Constructions of such generators are implicit in prior work of Kayal on lower bounds for the degree of annihilating polynomials. Our main contribution is a construction whose correctness relies on circuit complexity lower bounds rather than degree lower bounds.
Cite as

Robert Andrews. Algebraic Pseudorandomness in VNC⁰. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andrews:LIPIcs.CCC.2025.15,
  author =	{Andrews, Robert},
  title =	{{Algebraic Pseudorandomness in VNC⁰}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.15},
  URN =		{urn:nbn:de:0030-drops-237092},
  doi =		{10.4230/LIPIcs.CCC.2025.15},
  annote =	{Keywords: Polynomial identity testing, Algebraic circuits, Ideal Proof System}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.543
Symmetric Determinantal Representation of Weakly-Skew Circuits

Authors: Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.
Cite as

Bruno Grenet, Erich L. Kaltofen, Pascal Koiran, and Natacha Portier. Symmetric Determinantal Representation of Weakly-Skew Circuits. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 543-554, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{grenet_et_al:LIPIcs.STACS.2011.543,
  author =	{Grenet, Bruno and Kaltofen, Erich L. and Koiran, Pascal and Portier, Natacha},
  title =	{{Symmetric Determinantal Representation of Weakly-Skew Circuits}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{543--554},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.543},
  URN =		{urn:nbn:de:0030-drops-30426},
  doi =		{10.4230/LIPIcs.STACS.2011.543},
  annote =	{Keywords: algebraic complexity, determinant and permanent of symmetric matrices, formulas, skew circuits, Valiant’s classes}
}
Document
DOI: 10.4230/DagSemProc.09471.1
09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications

Authors: Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)

Abstract
From 15.11. to 20.11.2009, the Dagstuhl Seminar 09471 ``Computer-assisted proofs - tools, methods and applications '' 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

Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump. 09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:DagSemProc.09471.1,
  author =	{Brown, Malcolm B. and Kaltofen, Erich and Oishi, Shin'ichi and Rump, Siegfried M.},
  title =	{{09471 Abstracts Collection – Computer-assisted proofs - tools, methods and applications}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.1},
  URN =		{urn:nbn:de:0030-drops-25328},
  doi =		{10.4230/DagSemProc.09471.1},
  annote =	{Keywords: Verification methods, computer algebra, computer-assisted proofs}
}
Document
DOI: 10.4230/DagSemProc.09471.2
09471 Executive Summary – Computer-assisted proofs - tools, methods and applications

Authors: Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)

Abstract
From November 15-20, 2009, the Dagstuhl seminar on "Computer-assisted proofs - tools, methods and applications" continued a series of previous successful seminars. Participants from 10 different countries presented recent results in verification methods, computer algebra, and other computer-assisted-proof related areas. We had lively talks and discussions, during the regular times for talks, during meals and afterwards. In the following links to abstracts and/or the presentation are given were applicable.
Cite as

Malcolm B. Brown, Erich Kaltofen, Shin'ichi Oishi, and Siegfried M. Rump. 09471 Executive Summary – Computer-assisted proofs - tools, methods and applications. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:DagSemProc.09471.2,
  author =	{Brown, Malcolm B. and Kaltofen, Erich and Oishi, Shin'ichi and Rump, Siegfried M.},
  title =	{{09471 Executive Summary – Computer-assisted proofs - tools, methods and applications}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.2},
  URN =		{urn:nbn:de:0030-drops-25316},
  doi =		{10.4230/DagSemProc.09471.2},
  annote =	{Keywords: Verification methods, computer algebra, computer-assisted proofs}
}
Document
DOI: 10.4230/DagSemProc.09471.3
Interval Approaches to Reliable Control of Dynamical Systems

Authors: Andreas Rauh and Ekaterina Auer

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)

Abstract
Recently, we presented an implementation of interval-based algorithms which can be applied in real-time to control dynamical processes and to estimate internal states and disturbances. The approach is based on verified methods for sets of algebraic equations, ordinary differential equations as well as differential-algebraic equations. Due to this fact, the same program code can be used for two different tasks. On the one hand, we can use it online to estimate non-measurable internal system states which are necessary for nonlinear model-based control strategies. On the other hand, we can verify the admissibility and feasibility of these control strategies offline. Although we use the same code for the online and offline tasks, there is an important difference between them. While the computing time is of minor importance in offline applications, we have to guarantee that the necessary online computations are completed successfully in a predefined time interval. For that reason, the role of verification is slightly different depending on the task. In offline applications, our goal is to compute tightest possible bounds for the sets of all solutions to the control problem under consideration. In contrast to that, we restrict the online mode to a search for a single solution that matches all demands on feasibility of control inputs and admissibility of the trajectories of the state variables in a reliable way. To highlight the practical applicability of the underlying computational routines, we present the following cases for the use of verified solvers in real-time [1-3]. Case 1: Direct computation of feedforward control strategies with the help of differential-algebraic equation solvers. In this application, both verified and non-verified solvers can be used to determine open-loop control strategies for a dynamical system such that its output coincides with a predefined time response within given tolerances. This procedure corresponds to a numerical inversion of the dynamics of the system to be controlled. In this case, verified solvers are used to prove the existence of a control law within given physical bounds for the admissible range of the system inputs. Case 2: If measured data and their time derivatives are available, the same procedures as in case 1 can be used to estimate non-measured state variables as well as non-measurable disturbances. Since the verified algorithms used in this context are capable of propagating bounded measurement uncertainties, the quality of the state and disturbance estimates can be expressed in terms of the resulting interval widths. Moreover, assumptions about the parameters and the structure of the underlying model can be verified. Case 3: Routines for verified sensitivity analysis provide further information on the influence of variations of control inputs on the trajectories of the state variables. We present novel procedures implementing a sensitivity-based framework for model-predictive control. These procedures can be integrated directly in a feedback control structure. Sometimes it is necessary to combine verified and non-verified algorithms to solve a given control problem. In this case, it is important to certify the results of the algorithm appropriately. Based on the four-tier hierarchy presented in earlier works [4], we develop a measure for characterizing such mixed approaches. The presentation is concluded with simulation and experimental results for the example of temperature control of a distributed heating system. [1] Rauh, Andreas; Auer, Ekaterina: Applications of Verified DAE Solvers in Engineering, Intl. Workshop on Verified Computations and Related Topics, COE Lecture Note Vol. 15: Kyushu University, pp. 88-96, Karlsruhe, Germany, 2009. [2] Rauh, Andreas; Menn, Ingolf; Aschemann, Harald: Robust Control with State and Disturbance Estimation for Distributed Parameter Systems, Proc. of 15th Intl. Workshop on Dynamics and Control 2009, pp. 135-142, Tossa de Mar, Spain, 2009. [3] Rauh, Andreas; Auer, Ekaterina; Aschemann, Harald: Real-Time Application of Interval Methods for Robust Control of Dynamical Systems, CD-Proc. of IEEE Intl. Conference on Methods and Models in Automation and Robotics MMAR 2009, Miedzyzdroje, Poland, 2009. [4] Auer, Ekaterina; Luther, Wolfram: Numerical Verification Assessment in Computational Biomechanics, in A. Cuyt, W. Krämer, W. Luther, P. Markstein: Numerical Validation in Current Hardware Architectures, LNCS 5492, pp. 145-160, Springer-Verlag, Berlin, Heidelberg, 2009.
Cite as

Andreas Rauh and Ekaterina Auer. Interval Approaches to Reliable Control of Dynamical Systems. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{rauh_et_al:DagSemProc.09471.3,
  author =	{Rauh, Andreas and Auer, Ekaterina},
  title =	{{Interval Approaches to Reliable Control of Dynamical Systems}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.3},
  URN =		{urn:nbn:de:0030-drops-25120},
  doi =		{10.4230/DagSemProc.09471.3},
  annote =	{Keywords: Robust control, Ordinary differential equations, Differential-algebraic equations}
}
Document
DOI: 10.4230/DagSemProc.09471.4
Verification and Validation for Femur Prosthesis Surgery

Authors: Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)

Abstract
In this paper, we describe how verified methods we are developing in the course of the project TellHim&S (Interval Based Methods For Adaptive Hierarchical Models In Modeling And Simulation Systems) can be applied in the context of the biomechanical project PROREOP (Development of a new prognosis system to optimize patient-specific pre- operative surgical planning for the human skeletal system). On the one hand, it includes the use of verified hierarchical structures for reliable geometric modeling, object decomposition, distance computation and path planning. On the other hand, we cover such tasks as verification and validation assessment and propagation of differently described uncertainties through system models in engineering or mechanics.
Cite as

Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther. Verification and Validation for Femur Prosthesis Surgery. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{auer_et_al:DagSemProc.09471.4,
  author =	{Auer, Ekaterina and Cuypers, Roger and Dyllong, Eva and Kiel, Stefan and Luther, Wolfram},
  title =	{{Verification and Validation for Femur Prosthesis Surgery}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.4},
  URN =		{urn:nbn:de:0030-drops-25133},
  doi =		{10.4230/DagSemProc.09471.4},
  annote =	{Keywords: Graphical interface construction, superquadrics, 3D modeling, biomedical engineering}
}
Document
DOI: 10.4230/DagSemProc.06271.4
Bounds and algebraic algorithms in differential algebra: the ordinary case

Authors: Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Consider the Rosenfeld-Groebner algorithm for computing a regular decomposition of a radical differential ideal generated by a set of ordinary differential polynomials. This algorithm inputs a system of differential polynomials and a ranking on derivatives and constructs finitely many regular systems equivalent to the original one. The property of regularity allows to check consistency of the systems and membership to the corresponding differential ideals. We propose a bound on the orders of derivatives occurring in all intermediate and final systems computed by the Rosenfeld-Groebner algorithm and outline its proof. We also reduce the problem of conversion of a regular decomposition of a radical differential ideal from one ranking to another to a purely algebraic problem.
Cite as

Marc Moreno Maza, Oleg Golubitsky, Marina V. Kondratieva, and Alexey Ovchinnikov. Bounds and algebraic algorithms in differential algebra: the ordinary case. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{morenomaza_et_al:DagSemProc.06271.4,
  author =	{Moreno Maza, Marc and Golubitsky, Oleg and Kondratieva, Marina V. and Ovchinnikov, Alexey},
  title =	{{Bounds and algebraic algorithms in differential algebra: the ordinary case}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.4},
  URN =		{urn:nbn:de:0030-drops-10219},
  doi =		{10.4230/DagSemProc.06271.4},
  annote =	{Keywords: Differential algebra, Rosenfeld Groebner Algorithm}
}
Document
DOI: 10.4230/DagSemProc.06271.15
Two Families of Algorithms for Symbolic Polynomials

Authors: Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We wish to work with polynomials where the exponents are not known in advance, such as $x^{2n} - 1$. There are various operations we will want to be able to do, such as squaring the value to get $x^{4n}-2x^{2n}+1$, or differentiating it to get $2nx^{2n-1}$. Expressions of this sort arise frequently in practice, for example in the analysis of algorithms, and it is very difficult to work with them effectively in current computer algebra systems. We consider the case where multivariate polynomials can have exponents which are themselves integer-valued multivariate polynomials, and we present algorithms to compute their GCD and factorization. The algorithms fall into two families: algebraic extension methods and interpolation methods. The first family of algorithms uses the algebraic independence of $x$, $x^n$, $x^{n^2}$, $x^{nm}, etc, to solve related problems with more indeterminates. Some subtlety is needed to avoid problems with fixed divisors of the exponent polynomials. The second family of algorithms uses evaluation and interpolation of the exponent polynomials. While these methods can run into unlucky evaluation points, in many cases they can be more appealing. Additionally, we also treat the case of symbolic exponents on rational coefficients (e.g. $4^{n^2+n}-81$) and show how to avoid integer factorization.
Cite as

Stephen M. Watt. Two Families of Algorithms for Symbolic Polynomials. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.15,
  author =	{Watt, Stephen M.},
  title =	{{Two Families of Algorithms for Symbolic Polynomials}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.15},
  URN =		{urn:nbn:de:0030-drops-7933},
  doi =		{10.4230/DagSemProc.06271.15},
  annote =	{Keywords: Computer algebra, symbolic computation, factorization, gcd, symbolic exponents}
}
Document
DOI: 10.4230/DagSemProc.06271.1
06271 Abstracts Collection – Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
From 02.07.06 to 07.07.06, the Dagstuhl Seminar 06271 ``Challenges in Symbolic Computation Software'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. 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

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Abstracts Collection – Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.1,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Abstracts Collection – Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.1},
  URN =		{urn:nbn:de:0030-drops-7814},
  doi =		{10.4230/DagSemProc.06271.1},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid, symbolic-numerical methods, algorithm design, symbolic computation languages, systems and user interfaces}
}
Document
DOI: 10.4230/DagSemProc.06271.13
Pivot-Free Block Matrix Inversion

Authors: Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
We present a pivot-free deterministic algorithm for the inversion of block matrices. The method is based on the Moore-Penrose inverse and is applicable over certain general classes of rings. This improves on previous methods that required at least one invertible on-diagonal block, and that otherwise required row- or column-based pivoting, disrupting the block structure. Our method is applicable to any invertible matrix and does not require any particular blocks to invertible. This is achieved at the cost of two additional specialized matrix multiplications and, in some cases, requires the inversion to be performed in an extended ring.
Cite as

Stephen M. Watt. Pivot-Free Block Matrix Inversion. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{watt:DagSemProc.06271.13,
  author =	{Watt, Stephen M.},
  title =	{{Pivot-Free Block Matrix Inversion}},
  booktitle =	{Challenges in Symbolic Computation Software},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.13},
  URN =		{urn:nbn:de:0030-drops-7806},
  doi =		{10.4230/DagSemProc.06271.13},
  annote =	{Keywords: Linear algebra, block matrices, matrix inverse}
}
Document
DOI: 10.4230/DagSemProc.06271.2
06271 Executive Summary - Challenges in Symbolic Computation Software

Authors: Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Symbolic computation software allows mathematicians, scientists, engineers, or educators to deal with elaborate calculations using a computer. The applications range from introducing the experimental method in fields of pure mathematics to practical applications, for instance, in cryptology, robotics, or signal theory. The software includes mainstream commercial products such as Maple or Mathematica and highly specialized, public domain systems such as CoCoa, Macaulay2, or Singular. Symbolic computation software implements a variety of sophisticated algorithms on polynomials, matrices, combinatorial structures, and other mathematical objects in a multitude of different dense, sparse, or implicit (black box) representations. The subject of the seminar was innovation in algorithms and software, bringing algorithm designers, software builders, and software users together.
Cite as

Wolfram Decker, Mike Dewar, Erich Kaltofen, and Stephen M. Watt. 06271 Executive Summary - Challenges in Symbolic Computation Software. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{decker_et_al:DagSemProc.06271.2,
  author =	{Decker, Wolfram and Dewar, Mike and Kaltofen, Erich and Watt, Stephen M.},
  title =	{{06271 Executive Summary - Challenges in Symbolic Computation Software}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.2},
  URN =		{urn:nbn:de:0030-drops-7778},
  doi =		{10.4230/DagSemProc.06271.2},
  annote =	{Keywords: Symbolic computation, computer algebra, computational algebraic geometry, combinatorial methods in algebra, hybrid symbolic-numerical methods, algori}
}
Document
DOI: 10.4230/DagSemProc.06271.3
Adaptive Triangular System Solving

Authors: Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch

Published in: Dagstuhl Seminar Proceedings, Volume 6271, Challenges in Symbolic Computation Software (2006)

Abstract
Large-scale applications and software systems are getting increasingly complex. To deal with this complexity, those systems must manage themselves in accordance with high-level guidance from humans. Adaptive and hybrid algorithms enable this self-management of resources and structured inputs. In this talk, we first propose a classification of the different notions of adaptivity. For us, an algorithm is adaptive (or a poly-algorithm) when there is a choice at a high level between at least two distinct algorithms, each of which could solve the same problem. The choice is strategic, not tactical. It is motivated by an increase of the performance of the execution, depending on both input/output data and computing resources. Then we propose a new adaptive algorithm for the exact simultaneous resolution of several triangular systems over finite fields. The resolution of such systems is e.g. one of the two main operations in block Gaussian elimination. For solving triangular systems over finite fields, the block algorithm reduces to matrix multiplication and achieves the best known algebraic complexity. Exact matrix multiplication, together with matrix factorizations, over finite fields can now be performed at the speed of the highly optimized numerical BLAS routines. This has been established by the FFLAS and FFPACK libraries. In this talk we propose several practicable variants solving these systems: a pure recursive version, a reduction to the numerical dtrsm routine and a delaying of the modulus operation. Then a cascading scheme is proposed to merge these variants into an adaptive sequential algorithm. We then propose a parallelization of this resolution. The adaptive sequential algorithm is not the best parallel algorithm since its recursion induces a dependancy. A better parallel algorithm would be to first invert the matrix and then to multiply this inverse by the right hand side. Unfortunately the latter requires more total operations than the adaptive algorithm. We thus propose a coupling of the sequential algorithm and of the parallel one in order to get the best performances on any number of processors. The resulting cascading is then an adaptation to resources. This shows that the same process has been used both for adaptation to data and to resources. We thus propose a generic framework for the automatic adaptation of algorithms using recursive cascading.
Cite as

Jean-Guillaume Dumas, Clément Pernet, and Jean-Louis Roch. Adaptive Triangular System Solving. In Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, Volume 6271, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{dumas_et_al:DagSemProc.06271.3,
  author =	{Dumas, Jean-Guillaume and Pernet, Cl\'{e}ment and Roch, Jean-Louis},
  title =	{{Adaptive Triangular System Solving}},
  booktitle =	{Challenges in Symbolic Computation Software},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6271},
  editor =	{Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06271.3},
  URN =		{urn:nbn:de:0030-drops-7704},
  doi =		{10.4230/DagSemProc.06271.3},
  annote =	{Keywords: Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations}
}
  • Refine by Type
  • 25 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 1 2025
  • 1 2011
  • 4 2010
  • 1 2007
  • Show More...

  • Refine by Author
  • 5 Watt, Stephen M.
  • 4 Kaltofen, Erich
  • 2 Andrews, Robert
  • 2 Auer, Ekaterina
  • 2 Brown, Malcolm B.
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 20 DagSemProc

  • Refine by Classification
  • 3 Theory of computation → Algebraic complexity theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 4 computer algebra
  • 2 Symbolic computation
  • 2 Verification methods
  • 2 combinatorial methods in algebra
  • 2 computational algebraic geometry
  • 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