11 Search Results for "Kramer, Peter"


Document
Efficiently Reconfiguring a Connected Swarm of Labeled Robots

Authors: Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)


Abstract
When considering motion planning for a swarm of n labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, continuous, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, the total duration of an overall schedule can be bounded to 𝒪(d), which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots. We resolve these major open problems by (1) establishing a lower bound of Ω(√n) for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-hard to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.

Cite as

Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently Reconfiguring a Connected Swarm of Labeled Robots. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2022.17,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
  title =	{{Efficiently Reconfiguring a Connected Swarm of Labeled Robots}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.17},
  URN =		{urn:nbn:de:0030-drops-173028},
  doi =		{10.4230/LIPIcs.ISAAC.2022.17},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, makespan, connectivity, swarm robotics}
}
Document
Media Exposition
Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition)

Authors: Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
How can a set of identical mobile agents coordinate their motions to transform their arrangement from a given starting to a desired goal configuration? We consider this question in the context of actual physical devices called Catoms, which can perform reconfiguration, but need to maintain connectivity at all times to ensure communication and energy supply. We demonstrate and animate algorithmic results, in particular a proof of hardness, as well as an algorithm that guarantees constant stretch for certain classes of arrangements: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is in 𝒪(d), which is optimal up to constant factors.

Cite as

Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bourgeois_et_al:LIPIcs.SoCG.2022.65,
  author =	{Bourgeois, Julien and Fekete, S\'{a}ndor P. and Kosfeld, Ramin and Kramer, Peter and Piranda, Beno\^{i}t and Rieck, Christian and Scheffer, Christian},
  title =	{{Space Ants: Episode II - Coordinating Connected Catoms}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{65:1--65:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.65},
  URN =		{urn:nbn:de:0030-drops-160732},
  doi =		{10.4230/LIPIcs.SoCG.2022.65},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}
Document
08021 Abstracts Collection – Numerical Validation in Current Hardware Architectures

Authors: Wolfram Luther, Annie Cuyt, Walter Krämer, and Peter Markstein

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
From 06.01. to 11.01.2008, the Dagstuhl Seminar 08021 ``Numerical Validation in Current Hardware Architectures'' 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 Luther, Annie Cuyt, Walter Krämer, and Peter Markstein. 08021 Abstracts Collection – Numerical Validation in Current Hardware Architectures. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{luther_et_al:DagSemProc.08021.1,
  author =	{Luther, Wolfram and Cuyt, Annie and Kr\"{a}mer, Walter and Markstein, Peter},
  title =	{{08021 Abstracts Collection – Numerical Validation in Current Hardware Architectures}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.1},
  URN =		{urn:nbn:de:0030-drops-14785},
  doi =		{10.4230/DagSemProc.08021.1},
  annote =	{Keywords: Computer arithmetic, arbitrary precision, floating-point arithmetic standardization, language support, reliable libraries,high-precision special functions, reliablealgorithms, reliable floating-point and interval computing on different platforms}
}
Document
08021 Summary – Numerical Validation in Current Hardware Architectures

Authors: Annie Cuyt, Walter Krämer, Wolfram Luther, and Peter Markstein

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
Numerical validation in current hardware architectures - From embedded system to high-end computational grids Topics List of participants Schedule List of talks

Cite as

Annie Cuyt, Walter Krämer, Wolfram Luther, and Peter Markstein. 08021 Summary – Numerical Validation in Current Hardware Architectures. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{cuyt_et_al:DagSemProc.08021.2,
  author =	{Cuyt, Annie and Kr\"{a}mer, Walter and Luther, Wolfram and Markstein, Peter},
  title =	{{08021 Summary – Numerical Validation in Current Hardware Architectures}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.2},
  URN =		{urn:nbn:de:0030-drops-14334},
  doi =		{10.4230/DagSemProc.08021.2},
  annote =	{Keywords: Computer arithmetic, arbitrary precision, floating-point arithmetic standardization, language support, reliable libraries, high-precision special functions, reliablealgorithms, reliable floating-point and interval computing on different platforms}
}
Document
A Modified Staggered Correction Arithmetic with Enhanced Accuracy and Very Wide Exponent Range

Authors: Frithjof Blomquist, Werner Hofschuster, and Walter Krämer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
A so called staggered precision arithmetic is a special kind of a multiple precision arithmetic based on the underlying floating point data format (typically IEEE double format) and fast floating point operations as well as exact dot product computations. Due to floating point limitations it is not an arbitrary precision arithmetic. However, it typically allows computations using several hundred mantissa digits. A set of new modified staggered arithmetics for real and complex data as well as for real interval and complex interval data with very wide exponent range is presented. Some applications show the increased accuracy of computed results compared to ordinary staggered interval computations. The very wide exponent range of the new arithmetic operations allows computations far beyond the IEEE data formats. The new arithmetics would be extremly fast, if an exact dot product was available in hardware (the fused accumulate and add instruction is only one step in this direction).

Cite as

Frithjof Blomquist, Werner Hofschuster, and Walter Krämer. A Modified Staggered Correction Arithmetic with Enhanced Accuracy and Very Wide Exponent Range. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{blomquist_et_al:DagSemProc.08021.3,
  author =	{Blomquist, Frithjof and Hofschuster, Werner and Kr\"{a}mer, Walter},
  title =	{{A Modified Staggered Correction Arithmetic  with Enhanced Accuracy and Very Wide Exponent Range}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.3},
  URN =		{urn:nbn:de:0030-drops-14454},
  doi =		{10.4230/DagSemProc.08021.3},
  annote =	{Keywords: Staggered correction, multiple precision, C-XSC, interval computation, wide exponent range, reliable numerical computations, complex interval funct}
}
Document
A Note on Solving Problem 7 of the SIAM 100-Digit Challenge Using C-XSC

Authors: Mariana Kolberg, Walter Krämer, and Michael Zimmer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
C-XSC is a powerful C++ class library which simplifies the development of selfverifying numerical software. But C-XSC is not only a development tool, it also provides a lot of predefined highly accurate routines to compute reliable bounds for the solution to standard numerical problems. In this note we discuss the usage of a reliable linear system solver to compute the solution of problem 7 of the SIAM 100-digit challenge. To get the result we have to solve a 20 000 × 20 000 system of linear equations using interval computations. To perform this task we run our software on the advanced Linux cluster engine ALiCEnext located at the University of Wuppertal and on the high performance computer HP XC6000 at the computing center of the University of Karlsruhe. The main purpose of this note is to demonstrate the power/weakness of our approach to solve linear interval systems with a large dense system matrix using C-XSC and to get feedback from other research groups all over the world concerned with the topic described. We are very much interested to see comparisons concerning different methods/algorithms, timings, memory consumptions, and different hardware/software environments. It should be easy to adapt our main routine (see Section 3 below) to other programming languages, and different computing environments. Changing just one variable allows the generation of arbitrary large system matrices making it easy to do sound (reproducible and comparable) timings and to check for the largest possible system size that can be handled successfully by a specific package/environment.

Cite as

Mariana Kolberg, Walter Krämer, and Michael Zimmer. A Note on Solving Problem 7 of the SIAM 100-Digit Challenge Using C-XSC. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kolberg_et_al:DagSemProc.08021.4,
  author =	{Kolberg, Mariana and Kr\"{a}mer, Walter and Zimmer, Michael},
  title =	{{A Note on Solving Problem 7 of the SIAM 100-Digit Challenge Using C-XSC}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.4},
  URN =		{urn:nbn:de:0030-drops-14479},
  doi =		{10.4230/DagSemProc.08021.4},
  annote =	{Keywords: C-XSC, reliable computing, 100-digit challenge, reliable linear system solver, high performance computing, large dense linear systems}
}
Document
C-XSC and Closely Related Software Packages

Authors: Werner Hofschuster, Walter Krämer, and Markus Neher

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
C-XSC and Closely Related Software Packages

Cite as

Werner Hofschuster, Walter Krämer, and Markus Neher. C-XSC and Closely Related Software Packages. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{hofschuster_et_al:DagSemProc.08021.7,
  author =	{Hofschuster, Werner and Kr\"{a}mer, Walter and Neher, Markus},
  title =	{{C-XSC and Closely Related Software Packages}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.7},
  URN =		{urn:nbn:de:0030-drops-14425},
  doi =		{10.4230/DagSemProc.08021.7},
  annote =	{Keywords: Mathematical software, reliable computing, C-XSC, CoStLy, ACETAF}
}
Document
Fast (Parallel) Dense Linear Interval Systems Solvers in C-XSC Using Error Free Transformations and BLAS

Authors: Michael Zimmer and Walter Krämer

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
The traditional solver for linear interval systems available in C-XSC [6,1] is mathematically based on the Krawczyk[12] operator and modifications introduced by Rump[17]. The Krawczyk operator is composed of matrix/vector operations. These operations are realized in C-XSC with higest accuracy (only one final rounding) using a so called long accumulator (dotprecision variable). C-XSC dotprecision variables allow the error free computation of sums of floating point numbers as well as the error free computation of scalar products of floating point vectors. Thus, from a mathematical point of view these operations are perfect. Because actual hardware does not support these perfect scalar products all operations have to be realized by software. This fact leads to a tremendous time penalty (note: it has been shown that with modest additional hardware costs perfect scalar products can be made as fast as simple floating-point loops). To speed up the C-XSC scalar product software-operations we adapt the so called DotK algorithm as published in [14]. Error free transformations[14,3,4,10] are used as basic building blocks to develop summation and scalar product algorithms simulating a K-fold precision. Compared to the perfect C-XSC operations these operations are fast. They are more accurate than simple floating-point loops (but of course no longer perfect in the mathematical sense). The fast operations are available in C-XSC via the new data types DotK, IDotK, CDotk and CIDotK. These new data types are composed in such a way that traditional C-XSC code using dotprecision variables can be adapted with minimal effort. It is possible to switch (at runtime!) from perfect computations to fast operations using K-fold precision (K equal 0 means traditional dotprecision computations) and it is possible to hold intermediate results with corresponding error bounds for further summations or scalar product updates. The details are described in [19]. Additionaly, based on similar algorithms used in Intlab[16], BLAS and LAPACK libraries [2] are used in the O(n³) parts of the linear system solver. For matrix-matrix products, manipulation of the rounding mode of the processor is used to compute enclosures of the correct result. Comparing the traditional solver with the new version shows that the class of problems which are solvable with the new version is smaller than the class of problems which can be solved using the solver based on perfect operations. But it seems that for real world problems also the new solver is appropriate. Using the new solver based on BLAS and simulating a quadrupel precision (i.e. k==2) the speedup comes close to 200(!). The new solver is nearly as fast as the corresponding IntLab[16] solver verifylss. Solving a real linaer system of dimension 1000 on a Pentium 4 with 3.2GHz takes about 2.8 seconds. In all cases tested the accuracy of our new solver was better and in some cases significantly better than the accuracy of the corresponding IntLab results. The new solver also allows solving larger (dense) problems than its IntLab counterpart. We also show some examples where IntLab falls down whereas our new solver still works. A parallel version of this solver, based on ScaLAPACK, is also available. Unlike the previous parallel solver in C-XSC[5], this new solver does not depend on a root-node, which makes it possible to compute a verified solution even of very large linear systems. In the talk we will discuss the new data types in more detail, we will emphasize our modifications to the DotK algorithm taken from the literature [14,15], we will show time measurements and we will present results concerning the accuracy of the computed enclosures. Our results will also be compared to corresponding results computed with the IntLab package. We also will comment on hardware features and compiler options which can/should be used to get reliable results on different platforms efficiently. References: [1] Downloads: C-XSC library: http://www.math.uni-wuppertal.de/~xsc/xsc/cxsc.html Solvers: http://www.math.uni-wuppertal.de/~xsc/xsc/cxsc_software.html [2] L.S. Blackford, J. Demmel, J. Dongarra, I. Duff, S. Hammarling, G. Henry, M. Heroux, L. Kaufman, A. Lumsdaine, A. Petitet, R. Pozo, K. Remington, R. C. Whaley, An Updated Set of Basic Linear Algebra Subprograms (BLAS), ACM Trans. Math. Soft., 28-2 (2002), pp. 135--151. [3] Bohlender, G.; Walter, W.; Kornerup, P.; Matula, D.W.; Kornerup, P.; Matula, D.W.: Semantics for Exact Floating Point Operations. Proceedings, 10th IEEE Symposium on Computer Arithmetic, 26-28 June 1991, IEEE, 1991. [4] Dekker, T.J.: A floating-point technique for extending the available precision. Numer. Math., 18:224, 1971. [5] Grimmer, M.: Selbstverifizierende Mathematische Softwarewerkzeuge im High-Performance Computing. Konzeption, Entwicklung und Analyse am Beispiel der parallelen verifizierten Loesung linearer Fredholmscher Integralgleichungen zweiter Art. Logos Verlag, 2007. [6] Hofschuster, W.; Kraemer, W.: C-XSC 2.0: A C++ Library for Extended Scientific Computing. Numerical Software with Result Verification, Lecture Notes in Computer Science, Volume 2991/2004, Springer-Verlag, Heidelberg, pp. 15 - 35, 2004. [7] Kersten, Tim: Verifizierende rechnerinvariante Numerikmodule, Dissertation, University of Karlsruhe, 1998 [8] Klatte, Kulisch, Wiethoff, Lawo, Rauch: "C-XSC - A C++ Class Library for Extended Scientific Computing", Springer-Verlag, Heidelberg, 1993. Due to the C++ standardization (1998) and dramatic changes in C++ compilers over the last years this documentation describes no longer the actual C-XSC environment. Please refer to more accurate documentation (e.g.[1]) available from the web site of our research group: http... [9] Kirchner, R., Kulisch, U.: Hardware Support for Interval Arithmetic. Reliable Computing, Volume 12, Number 3, June 2006 , pp. 225-237(13). [10] Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms. Addison Wesley, 1969, vol. 2. [11] Kulisch, U.: Computer Arithmetic and Validity - Theory, Implementation. To appear. [12] Krawczyk, R.: Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing, 4:187-201, 1969. [13] Lerch, M.; Tischler, G.; Wolff von Gudenberg, J.; Hofschuster, W; Kraemer, W.: filib++, a Fast Interval Library Supporting Containment Computations. ACM TOMS, volume 32, number 2, pp. 299-324, 2006. [14] Ogita, T., Rump, S.M., Oishi, S.: Accurate sum and dot product. SIAM Journal on Scientific Computing, 26:6, 2005. [15] Oishi, S., Tanabe, K., Ogita, T., Rump, S.M., Yamanaka, N.: A Parallel Algorithm of Accurate Dot Product. Submitted for publication, 2007. [16] Rump, S.M.: Intlab - Interval Laboratory. Developments in Reliable Computing, pp. 77-104, 1999. [17] Rump, S.M.: Kleine Fehlerschranken bei Matrixproblemen, Dissertation, University of Karlsruhe, 1980 [18] Stroustrup, Bjarne: The C++-Programming Language, 3rd Edition, Addison-Wesley, 2000. [19] Zimmer, Michael: Laufzeiteffiziente, parallele Loeser fuer lineare Intervallgleichungssysteme in C-XSC, Master thesis, University of Wuppertal, 2007. AMS subject classification: 65H10, 15-04, 65G99, 65G10, 65-04

Cite as

Michael Zimmer and Walter Krämer. Fast (Parallel) Dense Linear Interval Systems Solvers in C-XSC Using Error Free Transformations and BLAS. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{zimmer_et_al:DagSemProc.08021.11,
  author =	{Zimmer, Michael and Kr\"{a}mer, Walter},
  title =	{{Fast (Parallel) Dense Linear Interval Systems Solvers in C-XSC Using Error Free Transformations and BLAS}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.11},
  URN =		{urn:nbn:de:0030-drops-14365},
  doi =		{10.4230/DagSemProc.08021.11},
  annote =	{Keywords: Error-free transformations, K-fold accuracy, accurate dot product, C-XSC, high accuracy, dense linear systems, verified computation.}
}
Document
On the Interoperability between Interval Software

Authors: Evgenija D. Popova

Published in: Dagstuhl Seminar Proceedings, Volume 8021, Numerical Validation in Current Hardware Architectures (2008)


Abstract
The increased appreciation of interval analysis as a powerful tool for controlling round-off errors and modelling with uncertain data leads to a growing number of diverse interval software. Beside in some other aspects, the available interval software differs with respect to the environment in which it operates and the provided functionality. Some specific software tools are built on the top of other more general interval software but there is no single environment supporting all (or most) of the available interval methods. On another side, most recent interval applications require a combination of diverse methods. It is difficult for the end-users to combine and manage the diversity of interval software tools, packages, and research codes, even the latter being accessible. Two recent initiatives: [1], directed toward developing of a comprehensive full-featured library of validated routines, and [3] intending to provide a general service framework for validated computing in heterogeneous environment, reflect the realized necessity for an integration of the available methods and software tools. It is commonly understood that quality comprehensive libraries are not compiled by a single person or small group of people over a short time [1]. Therefore, in this work we present an alternative approach based on interval software interoperability. While the simplest form of interoperability is the exchange of data files, we will focus on the ability to run a particular routine executable in one environment from within another software environment, and vice-versa, via communication protocols. We discuss the motivation, advantages and some problems that may appear in providing interoperability between the existing interval software. Since the general-purpose environments for scientific/technical computing like Matlab, Mathematica, Maple, etc. have several features not attributable to the compiled languages from one side and on another side most problem solving tools are developed in some compiled language for efficiency reasons, it is interesting to study the possibilities for interoperability between these two kinds of interval supporting environments. More specifically, we base our presentation on the interoperability between Mathematica [5] and external C-XSC programs [2] via MathLink communication protocol [4]. First, we discuss the portability and reliability of interval arithmetic in Mathematica. Then, we present MathLink technology for building external MathLink-compatible programs. On the example of a C-XSC function for solving parametric linear systems, called from within a Mathematica session, we demonstrate some advantages of interval software interoperability. Namely, expanded functionality for both environments, exchanging data without using intermediate files and without any conversion but under dynamics and interactivity in the communication, symbolic manipulation interfaces for the compiled language software that often make access to the external functionality from within Mathematica more convenient even than from its own native environment. Once established, MathLink connection to external interval libraries or problem-solving software opens up an array on new possibilities for the latter. References: [1] G. Corliss, R. B. Kearfott, N. Nedialkov, S. Smith: Towards an Interval Subroutine Library, Workshop on Reliable Engineering Computing, Svannah, Georgia, USA, Feb. 22-24, 2006. [2] W. Hofschuster: C-XSC: Highlights and new developments. In: Numerical Validation in Current Hardware Architectures. Number 08021 Dagstuhl Seminar, Internationales Begegnungs- und Forschungszentrum f"ur Informatik, Schloss Dagstuhl, Germany, 2008. [3] W. Luther, W. Kramer: Accurate Grid Computing, 12th GAMM-IMACS Int. Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2006), Duisburg, Sept. 26-29, 2006. [4] Ch. Miyaji, P. Abbot eds.: Mathlink: Network Programming with Mathematica, Cambridge Univ. Press, Cambridge, 2001. [5] Wolfram Research Inc.: Mathematica, Version 5.2, Champaign, IL, 2005.

Cite as

Evgenija D. Popova. On the Interoperability between Interval Software. In Numerical Validation in Current Hardware Architectures. Dagstuhl Seminar Proceedings, Volume 8021, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{popova:DagSemProc.08021.16,
  author =	{Popova, Evgenija D.},
  title =	{{On the Interoperability between Interval Software}},
  booktitle =	{Numerical Validation in Current Hardware Architectures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8021},
  editor =	{Annie Cuyt and Walter Kr\"{a}mer and Wolfram Luther and Peter Markstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08021.16},
  URN =		{urn:nbn:de:0030-drops-14501},
  doi =		{10.4230/DagSemProc.08021.16},
  annote =	{Keywords: Software interoperability, interfacing, interval software, C-XSC, MathLink, Mathematica}
}
Document
Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland

Authors: Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf

Published in: Dagstuhl Seminar Proceedings, Volume 5402, Perspectives Workshop (2006)


Abstract
Im Rahmen des Dagstuhl Perspektiven Workshop 05402 "Challenges for Software Engineering Research" haben führende Software Engineering Professoren den derzeitigen Stand der Softwaretechnik in Deutschland charakterisiert und Handlungsempfehlungen für Wirtschaft, Forschung und Politik abgeleitet. Das Manifest fasst die diese Empfehlungen und die Bedeutung und Entwicklung des Fachgebiets prägnant zusammen.

Cite as

Manfred Broy, Matthias Jarke, Manfred Nagl, Hans Dieter Rombach, Armin B. Cremers, Jürgen Ebert, Sabine Glesner, Martin Glinz, Michael Goedicke, Gerhard Goos, Volker Gruhn, Wilhelm Hasselbring, Stefan Jähnichen, Stefan Kowalewski, Bernd J. Krämer, Stefan Leue, Claus Lewerentz, Peter Liggesmeyer, Christoph Lüth, Barbara Paech, Helmut A. Partsch, Ilka Philippow, Lutz Prechelt, Andreas Rausch, Willem-Paul de Roever, Bernhard Rumpe, Gudula Rünger, Wilhelm Schäfer, Kurt Schneider, Andy Schürr, Walter F. Tichy, Bernhard Westfechtel, Wolf Zimmermann, and Albert Zündorf. Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland. In Perspectives Workshop. Dagstuhl Seminar Proceedings, Volume 5402, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{broy_et_al:DagSemProc.05402.1,
  author =	{Broy, Manfred and Jarke, Matthias and Nagl, Manfred and Rombach, Hans Dieter and Cremers, Armin B. and Ebert, J\"{u}rgen and Glesner, Sabine and Glinz, Martin and Goedicke, Michael and Goos, Gerhard and Gruhn, Volker and Hasselbring, Wilhelm and J\"{a}hnichen, Stefan and Kowalewski, Stefan and Kr\"{a}mer, Bernd J. and Leue, Stefan and Lewerentz, Claus and Liggesmeyer, Peter and L\"{u}th, Christoph and Paech, Barbara and Partsch, Helmut A. and Philippow, Ilka and Prechelt, Lutz and Rausch, Andreas and de Roever, Willem-Paul and Rumpe, Bernhard and R\"{u}nger, Gudula and Sch\"{a}fer, Wilhelm and Schneider, Kurt and Sch\"{u}rr, Andy and Tichy, Walter F. and Westfechtel, Bernhard and Zimmermann, Wolf and Z\"{u}ndorf, Albert},
  title =	{{Dagstuhl-Manifest zur Strategischen Bedeutung des Software Engineering in Deutschland}},
  booktitle =	{Perspectives Workshop},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5402},
  editor =	{Manfred Broy and Manfred Nagl and Hans Dieter Rombach and Matthias Jarke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05402.1},
  URN =		{urn:nbn:de:0030-drops-5853},
  doi =		{10.4230/DagSemProc.05402.1},
  annote =	{Keywords: Software Engineering, Software Technik, Strategie}
}
Document
Data Mining: The Next Generation

Authors: Raghu Ramakrishnan, Rakesh Agrawal, Johann-Christoph Freytag, Toni Bollinger, Christopher W. Clifton, Saso Dzeroski, Jochen Hipp, Daniel Keim, Stefan Kramer, Hans-Peter Kriegel, Ulf Leser, Bing Liu, Heikki Mannila, Rosa Meo, Shinichi Morishita, Raymond Ng, Jian Pei, Prabhakar Raghavan, Myra Spiliopoulou, Jaideep Srivastava, and Vicenc Torra

Published in: Dagstuhl Seminar Proceedings, Volume 4292, Perspectives Workshop: Data Mining: The Next Generation (2005)


Abstract
Data Mining (DM) has enjoyed great popularity in recent years, with advances in both research and commercialization. The first generation of DM research and development has yielded several commercially available systems, both stand-alone and integrated with database systems; produced scalable versions of algorithms for many classical DM problems; and introduced novel pattern discovery problems. In recent years, research has tended to be fragmented into several distinct pockets without a comprehensive framework. Researchers have continued to work largely within the parameters of their parent disciplines, building upon existing and distinct research methodologies. Even when they address a common problem (for example, how to cluster a dataset) they apply different techniques, different perspectives on what the important issues are, and different evaluation criteria. While different approaches can be complementary, and such a diversity is ultimately a strength of the field, better communication across disciplines is required if DM is to forge a distinct identity with a core set of principles, perspectives, and challenges that differentiate it from each of the parent disciplines. Further, while the amount and complexity of data continues to grow rapidly, and the task of distilling useful insight continues to be central, serious concerns have emerged about social implications of DM. Addressing these concerns will require advances in our theoretical understanding of the principles that underlie DM algorithms, as well as an integrated approach to security and privacy in all phases of data management and analysis. Researchers from a variety of backgrounds assembled at Dagstuhl to re-assess the current directions of the field, to identify critical problems that require attention, and to discuss ways to increase the flow of ideas across the different disciplines that DM has brought together. The workshop did not seek to draw up an agenda for the field of DM. Rather, it offers the participants’ perspective on two technical directions – compositionality and privacy – and describes some important application challenges that drove the discussion. Both of these directions illustrate the opportunities for crossdisciplinary research, and there was broad agreement that they represent important and timely areas for further work; of course, the choice of these directions as topics for discussion also reflects the personal interests and biases of the workshop participants.

Cite as

Raghu Ramakrishnan, Rakesh Agrawal, Johann-Christoph Freytag, Toni Bollinger, Christopher W. Clifton, Saso Dzeroski, Jochen Hipp, Daniel Keim, Stefan Kramer, Hans-Peter Kriegel, Ulf Leser, Bing Liu, Heikki Mannila, Rosa Meo, Shinichi Morishita, Raymond Ng, Jian Pei, Prabhakar Raghavan, Myra Spiliopoulou, Jaideep Srivastava, and Vicenc Torra. Data Mining: The Next Generation. In Perspectives Workshop: Data Mining: The Next Generation. Dagstuhl Seminar Proceedings, Volume 4292, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{ramakrishnan_et_al:DagSemProc.04292.1,
  author =	{Ramakrishnan, Raghu and Agrawal, Rakesh and Freytag, Johann-Christoph and Bollinger, Toni and Clifton, Christopher W. and Dzeroski, Saso and Hipp, Jochen and Keim, Daniel and Kramer, Stefan and Kriegel, Hans-Peter and Leser, Ulf and Liu, Bing and Mannila, Heikki and Meo, Rosa and Morishita, Shinichi and Ng, Raymond and Pei, Jian and Raghavan, Prabhakar and Spiliopoulou, Myra and Srivastava, Jaideep and Torra, Vicenc},
  title =	{{Data Mining: The Next Generation}},
  booktitle =	{Perspectives Workshop: Data Mining: The Next Generation},
  pages =	{1--33},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4292},
  editor =	{Rakesh Agrawal and Johann Christoph Freytag and Raghu Ramakrishnan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04292.1},
  URN =		{urn:nbn:de:0030-drops-2709},
  doi =		{10.4230/DagSemProc.04292.1},
  annote =	{Keywords: Data mining, databases, artificial intelligence, machine learning, statistics, semantics}
}
  • Refine by Author
  • 6 Krämer, Walter
  • 2 Cuyt, Annie
  • 2 Fekete, Sándor P.
  • 2 Hofschuster, Werner
  • 2 Kramer, Peter
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Motion path planning
  • 2 Theory of computation → Computational geometry

  • Refine by Keyword
  • 5 C-XSC
  • 2 Computer arithmetic
  • 2 Motion planning
  • 2 arbitrary precision
  • 2 bounded stretch
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 7 2008
  • 2 2022
  • 1 2005
  • 1 2006

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