@article{23731, abstract = {{ On 22 May 2000, the factorization of a pseudorandom polynomial of degree 1 048 543 over the binary field Z 2 was completed on a 4-processor Linux PC, using roughly 100 CPU-hours. The basic approach is a combination of the factorization software BIPOLAR and a parallel version of Cantor's multiplication algorithm. The PUB-library (Paderborn University BSP library) is used for the implementation of the parallel communication. }}, author = {{Bonorden, Olaf and von zur Gathen, Joachim and Gerhard, Jürgen and Müller, Olaf}}, issn = {{0163-5824}}, journal = {{ACM SIGSAM Bulletin}}, pages = {{16--18}}, title = {{{Factoring a binary polynomial of degree over one million}}}, doi = {{10.1145/504331.504333}}, year = {{2001}}, } @inproceedings{18152, abstract = {{Computing the spectral decomposition of a normal matrix is among the most frequent tasks to numerical mathematics. A vast range of methods are employed to do so, but all of them suffer from instabilities when applied to degenerate matrices, i.e., those having multiple eigenvalues. We investigate the spectral representation's effectivity properties on the sound formal basis of computable analysis. It turns out that in general the eigenvectors cannot be computed from a given matrix. If however the size of the matrix' spectrum (=number of different eigenvalues) is known in advance, it can be diagonalized effectively. Thus, in principle the spectral decomposition can be computed under remarkably weak non-degeneracy conditions.}}, author = {{Ziegler, Martin and Brattka, Vasco}}, booktitle = {{Proceedings of the 4th Workshop on Computability and Complexity in Analysis (CCA'2000)}}, isbn = {{9783540421979}}, issn = {{0302-9743}}, pages = {{378--388}}, title = {{{A Computable Spectral Theorem}}}, doi = {{10.1007/3-540-45335-0_23}}, volume = {{2064}}, year = {{2001}}, } @inproceedings{18166, abstract = {{What is the maximum number of edges of the d-dimensional hypercube, denoted by S(d,k), that can be sliced by k many hyperplanes? This question on combinatorial properties of Euclidean geometry arising from linear separability considerations in the theory of Perceptrons has become an issue on its own. We use computational and combinatorial methods to obtain new bounds on S(d,k), s<=8. These strengthen earlier results on hypercube cut numbers.}}, author = {{Ziegler, Martin and Emamy-Khansari, M. Reza}}, booktitle = {{Proceedings of the First International Conference on Discrete Models - Combinatorics, Computation and Geometry (DM-CCG'2001)}}, pages = {{155--164}}, title = {{{New Bounds for Hypercube Slicing Numbers}}}, volume = {{AA}}, year = {{2001}}, } @inproceedings{18168, abstract = {{We consider the classical LINEAR OPTIMIZATION Problem, but in the Turing rather than the RealRAM model. Asking for mere computability of a function's maximum over some closed domain, we show that the common presumptions 'full-dimensional' and `bounded' in fact cannot be omitted: The sound framework of Recursive Analysis enables us to rigorously prove this folkloristic observation! On the other hand, convexity of this domain may be weakened to connectedness, and even NON-linear functions turn out to be effectively optimizable.}}, author = {{Brattka, Vasco and Ziegler, Martin}}, booktitle = {{Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01)}}, pages = {{181--184}}, title = {{{Turing Computability of (Non-)Linear Optimization}}}, year = {{2001}}, } @inproceedings{18370, abstract = {{We present a new approximate occlusion-culling algorithm that in contrast to other algorithms, manages the objects of the scene in a 3D-sectorgraph. For generating a frame, as far as possible only the visible objects are rendered that can be found quickly by an edge of the graph. The algorithm allows a real-time navigation with over 20 frames per second in complex scenes consisting of over 10 millions of polygons. Moreover, approximation errors are very low.}}, author = {{Klein, Jan and Fischer, Matthias}}, booktitle = {{Proc. of 3. GI-Informatiktage 2001}}, pages = {{275 -- 278}}, title = {{{Occlusion Culling for Virtual Environments based on the 3D-Sectorgraph}}}, year = {{2001}}, } @inproceedings{16492, abstract = {{We present a new output-sensitive rendering algorithm, the randomized z-buffer algorithm. It renders an image of an arbitrary three-dimensional scene consisting of triangular primitives by reconstruction from a dynamically chosen set of random surface sample points. This approach is independent of mesh connectivity and topology. The resulting rendering time grows only logarithmically with the numbers of triangles in the scene. We were able to render walkthroughs of scenes of up to 10^14 triangles at interactive frame rates. Automatic identification of low detail scene components ensures that the rendering speed of the randomized z-buffer cannot drop below that of conventional z-buffer rendering. Experimental and analytical evidence is given that the image quality is comparable to that of common approaches like z-buffer rendering. The precomputed data structures employed by the randomized z-buffer allow for interactive dynamic updates of the scene. Their memory requirements grow only linearly with the number of triangles and allow for a scene graph based instantiation scheme to further reduce memory consumption.}}, author = {{Wand, Michael and Fischer, Matthias and Peter, Ingmar and Meyer auf der Heide, Friedhelm and Straßer, Wolfgang}}, booktitle = {{Proceedings of the 28th annual conference on Computer graphics and interactive techniques - SIGGRAPH '01}}, isbn = {{158113374X}}, title = {{{The randomized z-buffer algorithm}}}, doi = {{10.1145/383259.383299}}, year = {{2001}}, } @inbook{16493, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Graph-Theoretic Concepts in Computer Science}}, isbn = {{9783540427070}}, issn = {{0302-9743}}, title = {{{Data Management in Networks}}}, doi = {{10.1007/3-540-45477-2_2}}, volume = {{2204}}, year = {{2001}}, } @inbook{16494, author = {{Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, booktitle = {{Computational Science - ICCS 2001}}, isbn = {{9783540422334}}, issn = {{0302-9743}}, title = {{{Parallel Bridging Models and Their Impact on Algorithm Design}}}, doi = {{10.1007/3-540-45718-6_68}}, year = {{2001}}, } @book{16722, editor = {{Meyer auf der Heide, Friedhelm}}, isbn = {{9783540424932}}, issn = {{0302-9743}}, publisher = {{Springer }}, title = {{{Algorithms — ESA 2001, 9th Annual European Symposium Århus, Denmark}}}, doi = {{10.1007/3-540-44676-1}}, year = {{2001}}, } @phdthesis{19620, author = {{Rieping, Ingo}}, isbn = {{3-931466-80-9}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Communication in Parallel Systems-Models, Algorithms and Implementations}}}, volume = {{81}}, year = {{2000}}, } @phdthesis{19621, author = {{Westermann, Matthias}}, isbn = {{3-931466-89-2}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Caching in Networks: Non-Uniform Algorithms and Memory Capacity Constraints}}}, volume = {{90}}, year = {{2000}}, } @techreport{19733, author = {{Bonorden, Olaf and Rieping, Ingo and von Otte, Ingo and Juurlink, Bernhardus}}, title = {{{PUB-Library, Release 7.0, User Guide and Function Reference}}}, year = {{2000}}, } @inproceedings{19849, author = {{Bednara, M. and Beyer, O. and Teich, J. and Wanka, Rolf}}, booktitle = {{Proc. Int. Conf. on Application Specific Systems, Architectures, and Processors (ASAP)}}, isbn = {{0769507166}}, pages = {{299--308}}, title = {{{Tradeoff analysis and architecture design of a hybrid hardware/software sorter}}}, doi = {{10.1109/asap.2000.862400}}, year = {{2000}}, } @article{2143, author = {{Adler, Micah and Scheideler, Christian}}, journal = {{Theory Comput. Syst.}}, number = {{5/6}}, pages = {{337----391}}, title = {{{Efficient Communication Strategies for Ad Hoc Wireless Networks}}}, doi = {{10.1007/s002240010006}}, volume = {{33}}, year = {{2000}}, } @article{2145, author = {{Scheideler, Christian and Vöcking, Berthold}}, journal = {{SIAM J. Comput.}}, number = {{4}}, pages = {{1126----1155}}, title = {{{From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols}}}, doi = {{10.1137/S0097539799353431}}, volume = {{30}}, year = {{2000}}, } @inproceedings{2146, author = {{Berenbrink, Petra and Brinkmann, André and Scheideler, Christian}}, booktitle = {{PDPTA}}, title = {{{Distributed Path Selection for Storage Networks}}}, year = {{2000}}, } @inproceedings{2147, author = {{Czumaj, Artur and Scheideler, Christian}}, booktitle = {{SODA}}, pages = {{30----39}}, title = {{{Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma}}}, year = {{2000}}, } @article{2148, author = {{Czumaj, Artur and Scheideler, Christian}}, journal = {{Random Struct. Algorithms}}, number = {{3-4}}, pages = {{213----237}}, title = {{{Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma}}}, volume = {{17}}, year = {{2000}}, } @inproceedings{2149, author = {{Brinkmann, André and Salzwedel, Kay and Scheideler, Christian}}, booktitle = {{SPAA}}, pages = {{119----128}}, title = {{{Efficient, distributed data placement strategies for storage area networks (extended abstract)}}}, year = {{2000}}, } @inproceedings{2150, author = {{Czumaj, Artur and Scheideler, Christian}}, booktitle = {{STOC}}, pages = {{38----47}}, publisher = {{ACM}}, title = {{{A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract)}}}, year = {{2000}}, }