Volume

Dagstuhl Seminar Proceedings, Volume 5391

Publication Details

  • published at: 2006-01-31
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.05391.1
05391 Abstracts Collection – Algebraic and Numerical Algorithms and Computer-assisted Proofs

Authors: Bruno Buchberger, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump

Abstract
From 25.09.05 to 30.09.05, the Dagstuhl Seminar 05391 ``Algebraic and Numerical Algorithms and Computer-assisted Proofs'' 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. Links to extended abstracts or full papers are provided, if available.
Cite as

Bruno Buchberger, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump. 05391 Abstracts Collection – Algebraic and Numerical Algorithms and Computer-assisted Proofs. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{buchberger_et_al:DagSemProc.05391.1,
  author =	{Buchberger, Bruno and Oishi, Shin'ichi and Plum, Michael and Rump, Siegfried M.},
  title =	{{05391 Abstracts Collection – Algebraic and Numerical Algorithms and Computer-assisted Proofs}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.1},
  URN =		{urn:nbn:de:0030-drops-4555},
  doi =		{10.4230/DagSemProc.05391.1},
  annote =	{Keywords: Self-validating methods, computer algebra, computer-assisted proofs, real number algorithms}
}
Document
DOI: 10.4230/DagSemProc.05391.2
05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs

Authors: Bruno Buchberger, Christian Jansson, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump

Abstract
The common goal of self-validating methods and computer algebra methods is to solve mathematical problems with complete rigor and with the aid of computers. The seminar focused on several aspects of such methods for computer-assisted proofs.
Cite as

Bruno Buchberger, Christian Jansson, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump. 05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{buchberger_et_al:DagSemProc.05391.2,
  author =	{Buchberger, Bruno and Jansson, Christian and Oishi, Shin'ichi and Plum, Michael and Rump, Siegfried M.},
  title =	{{05391 Executive Summary – Numerical and Algebraic Algorithms and Computer-assisted Proofs}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.2},
  URN =		{urn:nbn:de:0030-drops-4549},
  doi =		{10.4230/DagSemProc.05391.2},
  annote =	{Keywords: Self-validating methods, computer algebra, computer-assisted proofs, real number algorithms}
}
Document
DOI: 10.4230/DagSemProc.05391.3
Compensated Horner Scheme

Authors: Philippe Langlois, Stef Graillat, and Nicolas Louvet

Abstract
Using error-free transformations, we improve the classic Horner Scheme (HS) to evaluate (univariate) polynomials in floating point arithmetic. We prove that this Compensated Horner Scheme (CHS) is as accurate as HS performed with twice the working precision. Theoretical analysis and experiments exhibit a reasonable running time overhead being also more interesting than double-double implementations. We introduce a dynamic and validated error bound of the CHS computed value. The talk presents these results together with a survey about error-free transformations and related hypothesis.
Cite as

Philippe Langlois, Stef Graillat, and Nicolas Louvet. Compensated Horner Scheme. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{langlois_et_al:DagSemProc.05391.3,
  author =	{Langlois, Philippe and Graillat, Stef and Louvet, Nicolas},
  title =	{{Compensated Horner Scheme}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.3},
  URN =		{urn:nbn:de:0030-drops-4423},
  doi =		{10.4230/DagSemProc.05391.3},
  annote =	{Keywords: Polynomial evaluation, Horner scheme, error-free transformation, floating point arithmetic, accuracy}
}
Document
DOI: 10.4230/DagSemProc.05391.4
Enclosure for the Biharmonic Equation

Authors: Borbála Fazekas, Michael Plum, and Christian Wieners

Abstract
In this paper we give an enclosure for the solution of the biharmonic problem and also for its gradient and Laplacian in the $L_2$-norm, respectively.
Cite as

Borbála Fazekas, Michael Plum, and Christian Wieners. Enclosure for the Biharmonic Equation. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fazekas_et_al:DagSemProc.05391.4,
  author =	{Fazekas, Borb\'{a}la and Plum, Michael and Wieners, Christian},
  title =	{{Enclosure for the Biharmonic Equation}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.4},
  URN =		{urn:nbn:de:0030-drops-4489},
  doi =		{10.4230/DagSemProc.05391.4},
  annote =	{Keywords: Biharmonic problem, enclosure, finite elements}
}
Document
DOI: 10.4230/DagSemProc.05391.5
Integration of reliable algorithms into modeling software

Authors: Wolfram Luther, Gerhard Haßlinger, Ekaterina Auer, Eva Dyllong, Daniela Traczinski, and Holger Traczinski

Abstract
In this note we discuss strategies that would enhance modern modeling and simulation software (MSS) with reliable routines using validated data types, controlled rounding, algorithmic differentiation and interval equation or initial value problem solver. Several target systems are highlighted. In stochastic traffic modeling, the computation of workload distributions plays a prominent role since they influence the quality of service parameters. INoWaTIV is a workload analysis tool that uses two different techniques: the polynomial factorization approach and the Wiener-Hopf factorization to determine the work-load distributions of GI/GI/1 and SMP/GI/1 service systems accurately. Two extensions of a multibody modeling and simulation software were developed to model kinematic and dynamic properties of multibody systems in a validated way. Furthermore, an interface was created that allows the computation of convex hulls and reliable lower bounds for the distances between subpav-ing-encoded objects constructed with SIVIA (Set Inverter Via Interval Analysis).
Cite as

Wolfram Luther, Gerhard Haßlinger, Ekaterina Auer, Eva Dyllong, Daniela Traczinski, and Holger Traczinski. Integration of reliable algorithms into modeling software. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{luther_et_al:DagSemProc.05391.5,
  author =	{Luther, Wolfram and Ha{\ss}linger, Gerhard and Auer, Ekaterina and Dyllong, Eva and Traczinski, Daniela and Traczinski, Holger},
  title =	{{Integration of reliable algorithms into modeling software}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.5},
  URN =		{urn:nbn:de:0030-drops-4441},
  doi =		{10.4230/DagSemProc.05391.5},
  annote =	{Keywords: Reliable algorithms, stochastic traffic modeling, multibody modeling tools, geometric modeling}
}
Document
DOI: 10.4230/DagSemProc.05391.6
Lurupa - Rigorous Error Bounds in Linear Programming

Authors: Christian Keil

Abstract
Linear Programming has numerous applications, e.g., operations research, relaxations in global optimization, computational geometry. Recently it has been shown that many real world problems exhibit numerical difficulties due to ill-conditioning. Lurupa is a software package for computing rigorous optimal value bounds. The package can handle point and interval problems. Numerical experience with the Netlib lp library is given.
Cite as

Christian Keil. Lurupa - Rigorous Error Bounds in Linear Programming. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{keil:DagSemProc.05391.6,
  author =	{Keil, Christian},
  title =	{{Lurupa - Rigorous Error Bounds in Linear Programming}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.6},
  URN =		{urn:nbn:de:0030-drops-4458},
  doi =		{10.4230/DagSemProc.05391.6},
  annote =	{Keywords: Linear programming, rigorous error bounds, netlib, interval arithmetic}
}
Document
DOI: 10.4230/DagSemProc.05391.7
Rigorous Results in Combinatorial Optimization

Authors: Christian Jansson

Abstract
Many current deterministic solvers for NP-hard combinatorial optimization problems are based on nonlinear relaxation techniques that use floating point arithmetic. Occasionally, due to solving these relaxations, rounding errors may produce erroneous results, although the deterministic algorithm should compute the exact solution in a finite number of steps. This may occur especially if the relaxations are ill-conditioned or ill-posed, and if Slater's constraint qualifications fail. We show how exact solutions can be obtained by rigorously bounding the optimal value of semidefinite relaxations, even in the ill-posed case. All rounding errors due to floating point arithmetic are taken into account.
Cite as

Christian Jansson. Rigorous Results in Combinatorial Optimization. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{jansson:DagSemProc.05391.7,
  author =	{Jansson, Christian},
  title =	{{Rigorous Results in Combinatorial Optimization}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.7},
  URN =		{urn:nbn:de:0030-drops-4467},
  doi =		{10.4230/DagSemProc.05391.7},
  annote =	{Keywords: Combinatorial Optimization, Semidefinite Programming, Ill-posed Problems, Verification Methods}
}
Document
DOI: 10.4230/DagSemProc.05391.8
Toward accurate polynomial evaluation in rounded arithmetic (short report)

Authors: James Demmel, Ioana Dumitriu, and Olga Holtz

Abstract
Given a multivariate real (or complex) polynomial $p$ and a domain $cal D$, we would like to decide whether an algorithm exists to evaluate $p(x)$ accurately for all $x in {cal D}$ using rounded real (or complex) arithmetic. Here ``accurately'' means with relative error less than 1, i.e., with some correct leading digits. The answer depends on the model of rounded arithmetic: We assume that for any arithmetic operator $op(a,b)$, for example $a+b$ or $a cdot b$, its computed value is $op(a,b) cdot (1 + delta)$, where $| delta |$ is bounded by some constant $epsilon$ where $0 < epsilon ll 1$, but $delta$ is otherwise arbitrary. This model is the traditional one used to analyze the accuracy of floating point algorithms. Our ultimate goal is to establish a decision procedure that, for any $p$ and $cal D$, either exhibits an accurate algorithm or proves that none exists. In contrast to the case where numbers are stored and manipulated as finite bit strings (e.g., as floating point numbers or rational numbers) we show that some polynomials $p$ are impossible to evaluate accurately. The existence of an accurate algorithm will depend not just on $p$ and $cal D$, but on which arithmetic operators and constants are available to the algorithm and whether branching is permitted in the algorithm. Toward this goal, we present necessary conditions on $p$ for it to be accurately evaluable on open real or complex domains ${cal D}$. We also give sufficient conditions, and describe progress toward a complete decision procedure. We do present a complete decision procedure for homogeneous polynomials $p$ with integer coefficients, ${cal D} = C^n$, using only arithmetic operations $+$, $-$ and $cdot$.
Cite as

James Demmel, Ioana Dumitriu, and Olga Holtz. Toward accurate polynomial evaluation in rounded arithmetic (short report). In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{demmel_et_al:DagSemProc.05391.8,
  author =	{Demmel, James and Dumitriu, Ioana and Holtz, Olga},
  title =	{{Toward accurate polynomial evaluation in rounded arithmetic (short report)}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.8},
  URN =		{urn:nbn:de:0030-drops-4477},
  doi =		{10.4230/DagSemProc.05391.8},
  annote =	{Keywords: Accurate polynomial evaluation, models or rounded arithmetic}
}
Document
DOI: 10.4230/DagSemProc.05391.9
Verification of Solutions for Almost Linear Complementarity Problems

Authors: Götz Alefeld and Zhengyu Wang

Abstract
We present a computational enclosure method for the solution of a class of nonlinear complementarity problems. The procedure also delivers a proof for the uniqueness of the solution.
Cite as

Götz Alefeld and Zhengyu Wang. Verification of Solutions for Almost Linear Complementarity Problems. In Algebraic and Numerical Algorithms and Computer-assisted Proofs. Dagstuhl Seminar Proceedings, Volume 5391, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{alefeld_et_al:DagSemProc.05391.9,
  author =	{Alefeld, G\"{o}tz and Wang, Zhengyu},
  title =	{{Verification of Solutions for  Almost Linear  Complementarity Problems}},
  booktitle =	{Algebraic and Numerical Algorithms and Computer-assisted Proofs},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5391},
  editor =	{Bruno Buchberger and Shin'ichi Oishi and Michael Plum and Sigfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05391.9},
  URN =		{urn:nbn:de:0030-drops-4431},
  doi =		{10.4230/DagSemProc.05391.9},
  annote =	{Keywords: Complementarity problems, verification of solutions}
}

Filters

  • Authors
  • A
  • Alefeld, Götz
  • Auer, Ekaterina
  • B
  • Buchberger, Bruno
  • D
  • Demmel, James
  • Dumitriu, Ioana
  • Dyllong, Eva
  • F
  • Fazekas, Borbála
  • G
  • Graillat, Stef
  • H
  • Haßlinger, Gerhard
  • Holtz, Olga
  • J
  • Jansson, Christian
  • K
  • Keil, Christian
  • L
  • Langlois, Philippe
  • Louvet, Nicolas
  • Luther, Wolfram
  • O
  • Oishi, Shin'ichi
  • P
  • Plum, Michael
  • R
  • Rump, Siegfried M.
  • T
  • Traczinski, Daniela
  • Traczinski, Holger
  • W
  • Wang, Zhengyu
  • Wieners, Christian

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