13 Search Results for "Oishi, Shin'ichi"

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.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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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

Published in: Dagstuhl Seminar Proceedings, Volume 5391, Algebraic and Numerical Algorithms and Computer-assisted Proofs (2006)

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}
}
  • Refine by Author
  • 4 Oishi, Shin'ichi
  • 4 Rump, Siegfried M.
  • 3 Auer, Ekaterina
  • 3 Plum, Michael
  • 2 Brown, Malcolm B.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 computer algebra
  • 4 computer-assisted proofs
  • 2 Self-validating methods
  • 2 Verification methods
  • 2 real number algorithms
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 9 2006
  • 4 2010

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact