Kaiserslautern - Fachbereich Informatik
Refine
Year of publication
- 2001 (12) (remove)
Document Type
- Report (12) (remove)
Has Fulltext
- yes (12)
Faculty / Organisational entity
We survey old and new results about optimal algorithms for summation of finite sequences and for integration of functions from Hölder or Sobolev spaces. First we discuss optimal deterministic and randornized algorithms. Then we add a new aspect, which has not been covered before on conferences
about (quasi-) Monte Carlo methods: quantum computation. We give a short introduction into this setting and present recent results of the authors on optimal quantum algorithms for summation and integration. We discuss comparisons between the three settings. The most interesting case for Monte
Carlo and quantum integration is that of moderate smoothness \(k\) and large dimension \(d\) which, in fact, occurs in a number of important applied problems. In that case the deterministic exponent is negligible, so the \(n^{-1/2}\) Monte Carlo and the \(n^{-1}\) quantum speedup essentially constitute the entire convergence rate.
In this work we propose a set of term-rewriting techniques for modelling object-oriented computation. Based on symbolic variants of explicit substitutions calculi, we show how to deal with imperative statements like assignment and sequence in specifications in a pure declarative style. Under our model, computation with classes and objects becomes simply normal form calculation, exactly as it is the case in term-rewriting based languages (for instance the functional languages). We believe this kind of unification between functions and
objects is important because it provides plausible alternatives for using the term-rewriting theory as an engine for supporting the formal and mechanical reasoning about object-oriented specifications.
Mobile Agenten im Internet
(2001)
Mobile Agenten haben sich in den letzten Jahren zunehmend in der Architektur und Programmierung verteilter Systeme bewährt. Es sind Programme, die einen Internen Zustand mit sich führen, während sie verschiedene, möglicherweise auf unterschiedlichen Plattformen basierende, Systeme besuchen. Auf dem jeweiligen System nehmen sie Dienste in Anspruch, indem sie entweder lokale Bibliotheken ansprechen, oder auf durch das System bereitgestellte Dienste zugreifen. Dabei müssen mobile Agenten sowohl alle vom Programm benötigten Daten, wie auch den gesamten Code mit sich führen. Zwar sind die Daten ein wichtiger (wenn nicht sogar der entscheidende) Teil eines Agenten, trotzdem wird in der Regel nicht als wertvoller, eigenständiger Part angesehen. Dies ist jedoch nicht immer ratsam, könnten doch Agenten am aktuellen Aufenthaltsort einen „Container" zurückzulassen um ihm anderen Agenten zur Verfügung zu stellen (natürlich erst nach erfolgter Zugriffskontrolle), bzw. die Daten erst dann auf ein Migrationsziel übertragen, wenn sich durch lokale Aufrufe des Systems herausgestellt hat, dass sie dort benötigt werden. Diese Arbeit ist zweigeteilt, insofern, als dass sie sich mit den zwei verschiedenen „Ebenen" der mobilen Agenten beschäftigt. Im ersten Teil werden die für die Migration und Nutzung der Resourcen notwendigen Aspekte besprochen. Dabei wird der Schwerpunkt auf die notwendige Unterstützung durch die Umgebung gelegt, wobei nicht eine neue integrierte Umgebung entworfen, sondern vielmehr die notwendigen Blöcke aufgezeigt werden sollen. Diese können dann als Teil eines Environments oder aber als eigentständige Komponente bereitsgestellt werden. Der zweite Teil beschäftigt sich mit den durch die Interaktion verschiedener Agenten entstehenden Probleme. Stichworte hierbei sind die Kostenkontrolle (wer bezahlt auf welche Art für in Anspruch genommene Dienste), Workflow Unterstützung, sowie Sicherheit in einem offenen, verteilten System, in dem es keine zentrale Überprüfung von Rechten und Identitäten geben kann. Abgeschlossen wird diese Ausarbeitung mit einer Bewertung der auf den beiden Ebenen gefundenen Problemen und Eigenheiten, wobei dann die Frage aufgeworfen wird, ob Agenten in der heutigen Form überhaupt sinnvoll sind.
The Analytic Blossom
(2001)
Blossoming is a powerful tool for studying and computing with Bézier and B-spline curves and surfaces - that is, for the investigation and analysis of polynomials and piecewise polynomials in geometric modeling. In this paper, we define a notion of the blossom for Poisson curves. Poisson curves are to analytic functions what Bézier curves are to polynomials - a representation adapted to geometric design. As in the polynomial setting, the blossom provides a simple, powerful, elegant and computationally meaningful way to analyze Poisson curves. Here, we
define the analytic blossom and interpret all the known algorithms for Poisson curves - subdivision, trimming, evaluation of the function and its derivatives, and conversion between the Taylor and the Poisson basis - in terms of this analytic blossom.
We introduce two novel techniques for speeding up the generation of digital \((t,s)\)-sequences. Based on these results a new algorithm for the construction of Owen's randomly permuted \((t,s)\)-sequences is developed and analyzed. An implementation of the new techniques is available at http://www.cs.caltech.edu/~ilja/libseq/index.html
Interleaved Sampling
(2001)
The sampling of functions is one of the most fundamental tasks in computer graphics, and occurs in a variety of different forms. The known sampling methods can roughly be grouped in two categories. Sampling on regular grids is simple and efficient, and the algorithms are often easy to built into graphics hardware. On the down side, regular sampling is prone to aliasing artifacts that are expensive to overcome. Monte Carlo methods, on the other hand,
mask the aliasing artifacts by noise. However due to the lack of coherence, these methods are more expensive and not weil suited for hardware implementations. In this paper, we introduce a novel sampling scheme where samples from several regular grids are a combined into a single irregular sampling pattern. The relative positions of the regular grids are themselves determined by Monte Carlo methods. This generalization obtained by interleaving yields,significantly improved quality compared to traditional approaches while at the same time preserving much of the advantageous coherency of regular sampling. We demonstrate the quality of the new sampling scheme with a number of applications ranging from supersampling over motion blur simulation to volume rendering. Due to the coherence in the interleaved samples, the method is optimally suited for implementations in graphics hardware.
The simulation of random fields has many applications in computer graphics such as e.g. ocean wave or turbulent wind field modeling. We present a new and strikingly simple synthesis algorithm for random fields on rank-1 lattices that requires only one Fourier transform independent of the dimension of the support of the random field. The underlying mathematical principle of discrete Fourier transforms on rank-1 lattices breaks the curse of dimension of the standard tensor product Fourier transform, i.e. the number of function values does not exponentially depend on the dimension, but can be chosen linearly.