3 Search Results for "von Gudenberg, J�rgen Wolff"


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
Interval Arithmetic and Standardization

Authors: Jürgen Wolff von Gudenberg

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


Abstract
Interval arithmetic is arithmetic for continuous sets. Floating-point intervals are intervals of real numbers with floating-point bounds. Operations for intervals can be efficiently implemented. There is an unanimous agreement, how to define the basic operations, if we exclude division by an interval containing zero. Hence, it should be standardized. For division by zero, two options are possible, the clean exception free interval arithmetic or the containment arithmetic. They can be standardized as options. Elementary functions for intervals can be defined. In some application areas loose evaluation of functions, i.e. evaluation over an interval which is not completely contained in the function domain, is recommended, In this case, however, a discontinuity flag has to be set to inform that Brouwer's fixed point theorem is no longer applicable in that case.

Cite as

Jürgen Wolff von Gudenberg. Interval Arithmetic and Standardization. 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{wolffvongudenberg:DagSemProc.08021.14,
  author =	{Wolff von Gudenberg, J\"{u}rgen},
  title =	{{Interval Arithmetic and Standardization}},
  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.14},
  URN =		{urn:nbn:de:0030-drops-14342},
  doi =		{10.4230/DagSemProc.08021.14},
  annote =	{Keywords: Intervals, containment sets, IEEE754r}
}
Document
Similarity in Programs

Authors: Andrew Walenstein, Mohammad El-Ramly, James R. Cordy, William S. Evans, Kiarash Mahdavi, Markus Pizka, Ganesan Ramalingam, and Jürgen Wolff von Gudenberg

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)


Abstract
An overview of the concept of program similarity is presented. It divides similarity into two types - syntactic and semantic - and provides a review of eight categories of methods that may be used to measure program similarity. A summary of some applications of these methods is included. The paper is intended to be a starting point for a more comprehensive analysis of the subject of similarity in programs, which is critical to understand if progress is to be made in fields such as clone detection.

Cite as

Andrew Walenstein, Mohammad El-Ramly, James R. Cordy, William S. Evans, Kiarash Mahdavi, Markus Pizka, Ganesan Ramalingam, and Jürgen Wolff von Gudenberg. Similarity in Programs. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{walenstein_et_al:DagSemProc.06301.11,
  author =	{Walenstein, Andrew and El-Ramly, Mohammad and Cordy, James R. and Evans, William S. and Mahdavi, Kiarash and Pizka, Markus and Ramalingam, Ganesan and von Gudenberg, J\"{u}rgen Wolff},
  title =	{{Similarity in Programs}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.11},
  URN =		{urn:nbn:de:0030-drops-9681},
  doi =		{10.4230/DagSemProc.06301.11},
  annote =	{Keywords: Computer programs, similarity, code clone, software comparison, program metrics, Levenshtein distance, parameterized difference, feature space, shared}
}
  • Refine by Author
  • 1 Cordy, James R.
  • 1 El-Ramly, Mohammad
  • 1 Evans, William S.
  • 1 Krämer, Walter
  • 1 Mahdavi, Kiarash
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 C-XSC
  • 1 Computer programs
  • 1 Error-free transformations
  • 1 IEEE754r
  • 1 Intervals
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2008
  • 1 2007

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