ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Articles  (114)
  • Computational geometry  (58)
  • 65F10  (56)
  • 1990-1994  (107)
  • 1980-1984  (7)
  • Mathematics  (114)
  • Energy, Environment Protection, Nuclear Power Engineering
Collection
  • Articles  (114)
Source
Keywords
Publisher
Years
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    A note on best conditioned preconditioners (1994)
    Springer
    BIT 34 (1994), S. 313-317 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65F15 ; 65F35 ; Toeplitz matrix ; circulant matrix ; best conditioned preconditioner ; preconditioned conjugate gradient method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We discuss the solution of Hermitian positive definite systemsAx=b by the preconditioned conjugate gradient method with a preconditionerM. In general, the smaller the condition numberκ(M −1/2 AM −1/2 ) is, the faster the convergence rate will be. For a given unitary matrixQ, letM Q = {Q*Λ N Q | Λ n is ann-by-n complex diagonal matrix} andM Q + ={Q*Λ n Q | Λ n is ann-by-n positive definite diagonal matrix}. The preconditionerM b that minimizesκ(M −1/2 AM −1/2 ) overM Q + is called the best conditioned preconditioner for the matrixA overM Q + . We prove that ifQAQ* has Young's Property A, thenM b is nothing new but the minimizer of ‖M −A‖ F overM Q . Here ‖ · ‖ F denotes the Frobenius norm. Some applications are also given here.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955879
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A numerical study of optimized sparse preconditioners (1994)
    Springer
    BIT 34 (1994), S. 177-204 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 15A06 ; 65F90 ; 65K10 ; Conjugate gradient method ; preconditioning ; incomplete factorization ; polynomial preconditioner ; matrix-free method ; Fourier analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners. Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n 1/4) andO(n 1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate. By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01955867
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Hartley preconditioners for Toeplitz systems generated by positive continuous functions (1994)
    Springer
    BIT 34 (1994), S. 367-371 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65F15 ; Topelitz matrix ; circulant matrix ; Hartley preconditioner ; conjugate gradient method ; generating function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM n is defined to be the minimizer of ‖T n −B n ‖ F over allB n εH n whereH n is the Hartley algebra. We show that if the generating functionf ofT n is a positive 2π-periodic continuous even function, then the spectrum of the preconditioned systemM n −1 T n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01935646
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Fast transforms for tridiagonal linear equations (1994)
    Springer
    BIT 34 (1994), S. 99-112 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65N06 ; Fourier Transform ; Sine Transform ; Toeplitz matrices ; elliptic differential equation ; finite difference method ; preconditioned conjugate gradient method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper we study the use of the Fourier, Sine and Cosine Transform for solving or preconditioning linear systems, which arise from the discretization of elliptic problems. Recently, R. Chan and T. Chan considered circulant matrices for solving such systems. Instead of using circulant matrices, which are based on the Fourier Transform, we apply the Fourier and the Sine Transform directly. It is shown that tridiagonal matrices arising from the discretization of an onedimensional elliptic PDE are connected with circulant matrices by congruence transformations with the Fourier or the Sine matrix. Therefore, we can solve such linear systems directly, using only Fast Fourier Transforms and the Sherman-Morrison-Woodbury formula. The Fast Fourier Transform is highly parallelizable, and thus such an algorithm is interesting on a parallel computer. Moreover, similar relations hold between block tridiagonal matrices and Block Toeplitz-plus-Hankel matrices of ordern 2×n 2 in the 2D case. This can be used to define in some sense natural approximations to the given matrix which lead to preconditioners for solving such linear systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01935019
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A workbench for computational geometry (1994)
    Springer
    Algorithmica 11 (1994), S. 404-428 
    Details
    ISSN: 1432-0541
    Keywords: Algorithms ; Computational geometry ; Implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe the design and implementation of a workbench for computational geometry. We discuss issues arising from this implementation, including comparisons of different algorithms for constant factors, code size, and ease of implementation. The workbench is not just a library of computational geometry algorithms and data structures, but is designed as a geometrical programming environment, providing tools for: creating, editing, and manipulating geometric objects; demonstrating and animating geometric algorithms; and, most importantly, for implementing and maintaining complex geometric algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187021
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    An improved technique for output-sensitive hidden surface removal (1994)
    Springer
    Algorithmica 11 (1994), S. 469-484 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden surface removal ; Ray shooting
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We derive a new output-sensitive algorithm for hidden surface removal in a collection ofn triangles, viewed from a pointz such that they can be ordered in an acyclic fashion according to their nearness toz. Ifk is the combinatorial complexity of the outputvisibility map, then we obtain a sophisticated randomized algorithm that runs in (randomized) timeO(n4/3 log2.89 n +k 3/5 n 4/5 + δ for anyδ 〉 0. The method is based on a new technique for tracing the visible contours using ray shooting.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01293267
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A provably fast linear-expected-time maxima-finding algorithm (1994)
    Springer
    Algorithmica 11 (1994), S. 501-524 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Maxima ; Probabilistic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper Bentleyet al. [1] presented some fast (low-multiplicative constants) linear-expected-time algorithms for finding the maxima ofN points chosen independently identically distributed (i.i.d.) from a Component Independent (CI) distribution. They also presented another algorithm, the Move-To-Front (MTF) algorithm, which empirical evidence suggests runs faster than the other algorithms. They conjectured that the MTF algorithm runs inN+o(N) expected time. In this paper we prove their conjecture forN points chosen i.i.d. from any two-dimensional distribution. The proof mixes probabilistic and amortized techniques.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01189991
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Point placement algorithms for Delaunay triangulation of polygonal domains (1994)
    Springer
    Algorithmica 12 (1994), S. 1-17 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Polygonal domain ; Finite-element mesh generation ; Edge-free circle ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377180
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    An optimal algorithm for the on-line closest-pair problem (1994)
    Springer
    Algorithmica 12 (1994), S. 18-29 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Closest pair ; Point location ; Centroid ; Amortization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm that computes the closest pair in a set ofn points ink-dimensional space on-line, inO(n logn) time. The algorithm only uses algebraic functions and, therefore, is optimal. The algorithm maintains a hierarchical subdivision ofk-space into hyperrectangles, which is stored in a binary tree. Centroids are used to maintain a balanced decomposition of this tree.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Ray shooting in polygons using geodesic triangulations (1994)
    Springer
    Algorithmica 12 (1994), S. 54-68 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray-shooting ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetP be a simple polygon withn vertices. We present a simple decomposition scheme that partitions the interior ofP intoO(n) so-called geodesic triangles, so that any line segment interior toP crosses at most 2 logn of these triangles. This decomposition can be used to preprocessP in a very simple manner, so that any ray-shooting query can be answered in timeO(logn). The data structure requiresO(n) storage andO(n logn) preprocessing time. By using more sophisticated techniques, we can reduce the preprocessing time toO(n). We also extend our general technique to the case of ray shooting amidstk polygonal obstacles with a total ofn edges, so that a query can be answered inO(√ logn) time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377183
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors (1994)
    Springer
    Algorithmica 12 (1994), S. 421-435 
    Details
    ISSN: 1432-0541
    Keywords: Spanning tree ; Steiner tree ; Heuristic algorithm ; Computational geometry ; Rectilinear distance ; Nearest neighbor ; Geographic nearest neighbor ; Decomposable search problem ; Range tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n 2 log n) toO(n log2 n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    Efficient ray shooting and hidden surface removal (1994)
    Springer
    Algorithmica 12 (1994), S. 30-53 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Multilevel data structures ; Hidden surface removal ; Output-sensitive
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+ɛ) preprocessing, for any fixedɛ 〉 0, withO(logn) query time. We also study the general ray-shooting problem in an arbitrary set of triangles. Here we present a structure that usesOn 4+ɛ) preprocessing and has a query time ofO(logn). We use the ray-shooting structure for curtains to obtain an algorithm for computing the view of a set of nonintersecting prolyhedra. For any ɛ 〉 0, we can obtain an algorithm with running time $$O(n^{1 + \varepsilon } \sqrt k )$$ , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01377182
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Algorithms for bichromatic line-segment problems and polyhedral terrains (1994)
    Springer
    Algorithmica 11 (1994), S. 116-132 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Line-segment intersection ; Segment trees ; Lines in space ; Polyhedral terrains ; Deterministic and randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider a variety of problems on the interaction between two sets of line segments in two and three dimensions. These problems range from counting the number of intersecting pairs between m blue segments andn red segments in the plane (assuming that two line segments are disjoint if they have the same color) to finding the smallest vertical distance between two nonintersecting polyhedral terrains in three-dimensional space. We solve these problems efficiently by using a variant of the segment tree. For the three-dimensional problems we also apply a variety of recent combinatorial and algorithmic techniques involving arrangements of lines in three-dimensional space, as developed in a companion paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182771
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    Variations on ray shooting (1994)
    Springer
    Algorithmica 11 (1994), S. 133-145 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting ; Half-plane range searching ; ES-trees
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We solve some problems related toray shooting in the plane, such as finding the first object hit by a query ray or counting the number of objects intersected by the query line. Our main results are an algorithm for finding the first hit when the objects are lines, and an algorithm for the case when the objects are segments. If the segments form simple polygons, this information can be used for reducing the complexity of the algorithms. The algorithms are efficient in space and in query time. Moreover, they are simple and therefore of practical use.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01182772
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems (1994)
    Springer
    Numerical algorithms 7 (1994), S. 1-16 
    Details
    ISSN: 1572-9265
    Keywords: Biconjugate gradients ; nonsymmetric linear systems ; 65N20 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The Bi-Conjugate Gradient (BCG) algorithm is the simplest and most natural generalization of the classical conjugate gradient method for solving nonsymmetric linear systems. It is well-known that the method suffers from two kinds of breakdowns. The first is due to the breakdown of the underlying Lanczos process and the second is due to the fact that some iterates are not well-defined by the Galerkin condition on the associated Krylov subspaces. In this paper, we derive a simple modification of the BCG algorithm, the Composite Step BCG (CSBCG) algorithm, which is able to compute all the well-defined BCG iterates stably, assuming that the underlying Lanczos process does not break down. The main idea is to skip over a step for which the BCG iterate is not defined.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02141258
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Fastiterative methods for least squares estimations (1994)
    Springer
    Numerical algorithms 6 (1994), S. 353-378 
    Details
    ISSN: 1572-9265
    Keywords: Least squares estimations ; Toeplitz matrix ; circulant matrix ; preconditioned conjugate gradient method ; signal prediction ; linear prediction ; covariance matrix ; windowing methods ; finite impulse response (FIR) system identification ; 65F10 ; 65F15 ; 43E10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Least squares estimations have been used extensively in many applications, e.g. system identification and signal prediction. When the stochastic process is stationary, the least squares estimators can be found by solving a Toeplitz or near-Toeplitz matrix system depending on the knowledge of the data statistics. In this paper, we employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Our proposed circulant preconditioners are derived from the spectral property of the given stationary process. In the case where the spectral density functions(θ) of the process is known, we prove that ifs(θ) is a positive continuous function, then the spectrum of the preconditioned system will be clustered around 1 and the method converges superlinearly. However, if the statistics of the process is unknown, then we prove that with probability 1, the spectrum of the preconditioned system is still clustered around 1 provided that large data samples are taken. For finite impulse response (FIR) system identification problems, our numerical results show that annth order least squares estimator can usually be obtained inO(n logn) operations whenO(n) data samples are used. Finally, we remark that our algorithm can be modified to suit the applications of recursive least squares computations with the proper use of sliding window method arising in signal processing applications.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02142678
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    A composite step conjugate gradients squared algorithm for solving nonsymmetric linear systems (1994)
    Springer
    Numerical algorithms 7 (1994), S. 17-32 
    Details
    ISSN: 1572-9265
    Keywords: Lanczos method ; conjugate gradients squared algorithm ; breakdowns ; composite step ; 65F10 ; 65F25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a new and more stable variant of the CGS method [27] for solving nonsymmetric linear systems. The method is based on squaring the Composite Step BCG method, introduced recently by Bank and Chan [1,2], which itself is a stabilized variant of BCG in that it skips over steps for which the BCG iterate is not defined and causes one kind of breakdown in BCG. By doing this, we obtain a method (Composite Step CGS or CSCGS) which not only handles the breakdowns described above, but does so with the advantages of CGS, namely, no multiplications by the transpose matrix and a faster convergence rate than BCG. Our strategy for deciding whether to skip a step does not involve any machine dependent parameters and is designed to skip near breakdowns as well as produce smoother iterates. Numerical experiments show that the new method does produce improved performance over CGS on practical problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02141259
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    BiCGstab(l) and other hybrid Bi-CG methods (1994)
    Springer
    Numerical algorithms 7 (1994), S. 75-109 
    Details
    ISSN: 1572-9265
    Keywords: Bi-Conjugate gradients ; non-symmetric linear systems ; CGS ; Bi-CGSTAB ; iterative solvers ; ORTHODIR ; Krylov subspace ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is well-known that Bi-CG can be adapted so that the operations withA T can be avoided, and hybrid methods can be constructed in which it is attempted to further improve the convergence behaviour. Examples of this are CGS, Bi-CGSTAB, and the more general BiCGstab(l) method. In this paper it is shown that BiCGstab(l) can be implemented in different ways. Each of the suggested approaches has its own advantages and disadvantages. Our implementations allow for combinations of Bi-CG with arbitrary polynomial methods. The choice for a specific implementation can also be made for reasons of numerical stability. This aspect receives much attention. Various effects have been illustrated by numerical examples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02141261
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Treatment of near-breakdown in the CGS algorithm (1994)
    Springer
    Numerical algorithms 7 (1994), S. 33-73 
    Details
    ISSN: 1572-9265
    Keywords: Conjugate gradient ; Lanczos' method ; systems of linear equations ; orthogonal polynomials ; 65F05 ; 65F10 ; 65F25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Lanczos' method for solving the system of linear equationsAx=b consists in constructing a sequence of vectors (x k ) such thatr k =b−Ax k =P k (A)r 0 wherer 0=b−Ax 0.P k is an orthogonal polynomial which is computed recursively. The conjugate gradient squared algorithm (CGS) consists in takingr k =P k 2 (A)r0. In the recurrence relation forP k , the coefficients are given as ratios of scalar products. When a scalar product in a denominator is zero, then a breakdown occurs in the algorithm. When such a scalar product is close to zero, then rounding errors can seriously affect the algorithm, a situation known as near-breakdown. In this paper it is shown how to avoid near-breakdown in the CGS algorithm in order to obtain a more stable method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02141260
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes (1994)
    Springer
    Numerical algorithms 8 (1994), S. 329-346 
    Details
    ISSN: 1572-9265
    Keywords: Unstructured meshes ; non-nested coarse meshes ; additive Schwarz algorithm ; optimal convergence rate ; 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02142697
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation (1993)
    Springer
    BIT 33 (1993), S. 634-646 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65N22 ; 65N35 ; 65N55 ; Dirichlet problem ; Poisson's equation ; piecewise Hermite cubics ; Gauss points ; eigenvalues ; eigenfunctions ; H 1-norm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH 1-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01990539
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems, part II: Convergence theory (1993)
    Springer
    Numerische Mathematik 65 (1993), S. 469-492 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N30 ; 65N55
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385763
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations (1993)
    Springer
    Numerische Mathematik 64 (1993), S. 213-240 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ∈ ℝ N, N , withA nonsingular, andb ∈ ℝ N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01388688
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems, part I: Algorithms and numerical results (1993)
    Springer
    Numerische Mathematik 65 (1993), S. 445-468 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We describe sequential and parallel algorithms based on the Schwarz alternating method for the solution of mixed finite element discretizations of elliptic problems using the Raviart-Thomas finite element spaces. These lead to symmetric indefinite linear systems and the algorithms have some similarities with the traditional block Gauss-Seidel or block Jacobi methods with overlapping blocks. The indefiniteness requires special treatment. The sub-blocks used in the algorithm correspond to problems on a coarse grid and some overlapping subdomains and is based on a similar partition used in an algorithm of Dryja and Widlund for standard elliptic problems. If there is sufficient overlap between the subdomains, the algorithm converges with a rate independent of the mesh size, the number of subdomains and discontinuities of the coefficients. Extensions of the above algorithms to the case of local grid refinement is also described. Convergence theory for these algorithms will be presented in a subsequent paper.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385762
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Robustness of multi-grid applied to anisotropic equations on convex domains and on domains with re-entrant corners (1993)
    Springer
    Numerische Mathematik 66 (1993), S. 373-398 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We analyse multi-grid applied to anisotropic equations within the framework of smoothing and approximation-properties developed by Hack busch. For a model anisotropic equation on a square, we give an up-till-now missing proof of an estimate concerning the approximation property which is essential to show robustness. Furthermore, we show a corresponding estimate for a model anisotropic equation on an L-shaped domain. The existing estimates for the smoothing property are not suitable to prove robustness for either 2-cyclic Gauss-Seidel smoothers or for less regular problems such as our second model equation. For both cases, we give sharper estimates. By combination of our results concerning smoothing- and approximation-properties, robustness of W-cycle multi-grid applied to both our model equations will follow for a number of smoothers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385703
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    An efficient algorithm for finding the CSG representation of a simple polygon (1993)
    Springer
    Algorithmica 10 (1993), S. 1-23 
    Details
    ISSN: 1432-0541
    Keywords: Constructive solid geometry ; Computational geometry ; Boundary representation ; Monotone boolean formulae ; Incremental convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Modeling two-dimensional and three-dimensional objects is an important theme in computer graphics. Two main types of models are used in both cases: boundary representations, which represent the surface of an object explicitly but represent its interior only implicitly, and constructive solid geometry representations, which model a complex object, surface and interior together, as a boolean combination of simpler objects. Because neither representation is good for all applications, conversion between the two is often necessary. We consider the problem of converting boundary representations of polyhedral objects into constructive solid geometry (CSG) representations. The CSG representations for a polyhedronP are based on the half-spaces supporting the faces ofP. For certain kinds of polyhedra this problem is equivalent to the corresponding problem for simple polygons in the plane. We give a new proof that the interior of each simple polygon can be represented by a monotone boolean formula based on the half-planes supporting the sides of the polygon and using each such half-plane only once. Our main contribution is an efficient and practicalO(n logn) algorithm for doing this boundary-to-CSG conversion for a simple polygon ofn sides. We also prove that such nice formulae do not always exist for general polyhedra in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01908629
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    Geometric knapsack problems (1993)
    Springer
    Algorithmica 10 (1993), S. 399-427 
    Details
    ISSN: 1432-0541
    Keywords: Knapsack problems ; Computational geometry ; Convexity ; Dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following “fence enclosure” problem: given a setS ofn points in the plane with valuesv i ≥ 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the “value” of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01769706
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    The slab dividing approach to solve the EuclideanP-Center problem (1993)
    Springer
    Algorithmica 9 (1993), S. 1-22 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Givenn demand points on the plane, the EuclideanP-Center problem is to findP supply points, such that the longest distance between each demand point and its closest supply point is minimized. The time complexity of the most efficient algorithm, up to now, isO(n 2 p−1· logn). In this paper, we present an algorithm with time complexityO(n 0(√P)).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185335
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Maximumk-covering of weighted transitive graphs with applications (1993)
    Springer
    Algorithmica 9 (1993), S. 84-100 
    Details
    ISSN: 1432-0541
    Keywords: Transitive graphs ; Network flow ; VLSI layout ; Computational geometry ; Integer sequences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn 2)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn 2), wheren is the input size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01185340
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    Duality of constrained Voronoi diagrams and Delaunay triangulations (1993)
    Springer
    Algorithmica 9 (1993), S. 142-155 
    Details
    ISSN: 1432-0541
    Keywords: Voronoi diagram ; Delaunay triangulation ; Duality ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We introduce theconstrained Voronoi diagram of a planar straight-line graph containingn vertices or sites where the line segments of the graph are regarded as obstacles, and show that an extended version of this diagram is the dual of theconstrained Delaunay triangulation. We briefly discussO(n logn) algorithms for constructing the extended constrained Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188709
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Fast linear expected-time algorithms for computing maxima and convex hulls (1993)
    Springer
    Algorithmica 9 (1993), S. 168-183 
    Details
    ISSN: 1432-0541
    Keywords: Maxima ; Convex hulls ; Computational geometry ; Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N1−1/K log1/K N) expected scalar comparisons, for fixedK≥ 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK ≥ 2, an algorithm computes the convex hull of the set in 2KN + O(N1−1/K log1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01188711
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    A semidynamic construction of higher-order voronoi diagrams and its randomized analysis (1993)
    Springer
    Algorithmica 9 (1993), S. 329-356 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Dynamic algorithm ; Randomized complexity analysis ; Orderk Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the order≤k Voronoi diagrams, can be done inO(n logn+k 3n) expected time and O(k2n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ⌈(d+1)/2⌉+1 n ⌊(d+1)/2⌋) and space complexityO(k ⌈(d+1)/2⌉ n ⌊(d+1)/2⌋). The algorithm is simple and experimental results are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228508
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    The searching over separators strategy to solve some NP-hard problems in subexponential time (1993)
    Springer
    Algorithmica 9 (1993), S. 398-423 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; NP-hardness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator which divides the input points into two parts,A d andC d, in such a way that after solving these two subproblems withA d andC d as inputs, respectively, we can merge the respective subsolutions into an optimal solution. Let us further assume that this problem is an optimization problem. In this case our searching over separators strategy will use a separator generator to generate all possible separators. For each separator, the problem is solved by the divide-and-conquer strategy. If the separator generator is guaranteed to generate the desired separator existing in an optimal solution, our searching over separators strategy will always produce an optimal solution. The performance of our approach will critically depend upon the performance of the separator generator. It will perform well if the total number of separators generated is relatively small. We apply this approach to solve the discrete EuclideanP-median problem (DEPM), the discrete EuclideanP-center problem (DEPC), the EuclideanP-center problem (EPC), and the Euclidean traveling salesperson problem (ETSP). We propose $$O(n^{o(\sqrt P )} )$$ algorithms for the DEPM problem, the DEPC problem, and the EPC problem, and we propose an $$O(n^{o(\sqrt n )} )$$ algorithm for the ETSP problem, wheren is the number of input points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01228511
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    Electronic Resource
    Electronic Resource
    Ray shooting on triangles in 3-space (1993)
    Springer
    Algorithmica 9 (1993), S. 471-494 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Ray shooting on triangles ; Arrangements of hyperplanes ; 3-Space ; Plücker coordinates ; Isotopy classes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR 3 into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems: 1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles. 2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term. 3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term. 4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra. 5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187036
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Constructing strongly convex approximate hulls with inaccurate primitives (1993)
    Springer
    Algorithmica 9 (1993), S. 534-560 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Epsilon Geometry ; Approximate computations ; Robust algorithms ; Strongly convex polygons ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The first half of this paper introducesEpsilon Geometry, a framework for the development of robust geometric algorithms using inaccurate primitives. Epsilon Geometry is based on a very general model of imprecise computations, which includes floating-point and rounded-integer arithmetic as special cases. The second half of the paper introduces the notion of a (−ɛ)-convex polygon, a polygon that remains convex even if its vertices are all arbitrarily displaced by a distance ofɛ of less, and proves some interesting properties of such polygons. In particular, we prove that for every point set there exists a (−ɛ)-convex polygonH such that every point is at most 4ɛ away fromH. Using the tools of Epsilon Geometry, we develop robust algorithms for testing whether a polygon is (−ɛ)-convex, for testing whether a point is inside a (−ɛ)-convex polygon, and for computing a (−ɛ)-convex approximate hull for a set of points.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190154
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    Algorithms for projecting points to give the most uniform distribution with applications to hashing (1993)
    Springer
    Algorithmica 9 (1993), S. 572-590 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Duality transform ; Hashing ; Intersection-reporting algorithm ; Linear-space algorithm ; Plane sweep ; Projection ; Simplex range search ; Topological walk
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents several algorithms for projecting points so as to give the most uniform distribution. Givenn points in the plane and an integerb, the problem is to find an optimal angleθ ofb equally spaced parallel lines such that points are distributed most uniformly over buckets (regions bounded by two consecutive lines). An algorithm is known only in thetight case in which the two extreme lines are the supporting lines of the point set. The algorithm requiresO(bn2 logn) time and On2+bn) space to find an optimal solution. In this paper we improve the algorithm both in time and space, based on duality transformation. Two linear-space algorithms are presented. One runs in On2+K log n+bn) time, whereK is the number of intersections in the transformed plane.K is shown to beO(@#@ n2+bn@#@) based on a new counting scheme. The other algorithm is advantageous ifb 〈 √n. It performs a simplex range search in each slab to enumerate all the lines that intersectbucket lines, and runs in O(b0.610n1.695+K logn) time. It is also shown that the problem can be solved in polynomial time even in therelaxed case. Its one-dimensional analogue is especially related to the design of an optimal hash function for a static set of keys.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190156
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Splitting a configuration in a simplex (1993)
    Springer
    Algorithmica 9 (1993), S. 649-668 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Partition of point sets ; Assignment problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a new method of partition, namedπ-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and letπ be a sequence of nonnegative integers π1, ..., nd+1 satisfying σ i=1 d+1 π1=n Theπ-splitter of (T, S) is a pointG inT such thatT(G;i) contains at leastπ i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting. The existence of aπ-splitting is shown for any (T, S) andπ, and two efficient algorithms for finding such a splitting are given. One runs inO(d2n logn + d3n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01190161
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Some comparison theorems for nonnegative splittings of matrices (1993)
    Springer
    Numerische Mathematik 65 (1993), S. 245-252 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 15A06
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary In a recent paper the author has proposed some theorems on the comparison of the asymptotic rates of convergence of two nonnegative splittings. They extended the corresponding result of Miller and Neumann and implied the earlier theorems of Varga, Beauwens, Csordas and Varga. An open question by Miller and Neumann, which additional and appropriate conditions should be imposed to obtain strict inequality, was also answered. This article continues to investigate the comparison theorems for nonnegative splittings. The new results extend and imply the known theorems by the author, Miller and Neumann.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385750
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    On the convergence rate of the conjugate gradients in presence of rounding errors (1993)
    Springer
    Numerische Mathematik 65 (1993), S. 301-317 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65B99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We investigate here rounding error effects on the convergence rate of the conjugate gradients. More precisely, we analyse on both theoretical and experimental basis how finite precision arithmetic affects known bounds on iteration numbers when the spectrum of the system matrix presents small or large isolated eigenvalues.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385754
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    On additive Schwarz preconditioners for sparse grid discretizations (1993)
    Springer
    Numerische Mathematik 66 (1993), S. 449-463 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65F35 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k 2 ·2 k/2 ), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385707
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    An analysis of the composite step biconjugate gradient method (1993)
    Springer
    Numerische Mathematik 66 (1993), S. 295-319 
    Details
    ISSN: 0945-3245
    Keywords: 65N20 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The composite step biconjugate gradient method (CSBCG) is a simple modification of the standard biconjugate gradient algorithm (BCG) which smooths the sometimes erratic convergence of BCG by computing only a subset of the iterates. We show that 2×2 composite steps can cure breakdowns in the biconjugate gradient method caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. We also prove a “best approximation” result for the method. Some numerical illustrations showing the effect of roundoff error are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385699
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    A generalized ADI iterative method (1993)
    Springer
    Numerische Mathematik 66 (1993), S. 215-233 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The ADI iterative method for the solution of Sylvester's equationAX−XB=C proceeds by strictly alternating between the solution of the two equations $$\begin{gathered} \left( {A - \delta _{k + 1} I} \right)X_{2k + 1} = X_{2k} \left( {B - \delta _{k + 1} I} \right) + C, \hfill \\ X_{2k + 2} \left( {B - \tau _{k + 1} I} \right) = \left( {A - \tau _{k + 1} I} \right)X_{2k + 1} - C, \hfill \\ \end{gathered} $$ fork=0, 1, 2,... HereX o is a given initial approximate solution, and the δ k andτ k are real or complex parameters chosen so that the computed approximate solutionsX k converge rapidly to the solutionX of the Sylvester equation ask increases. This paper discusses the possibility of solving one of the equations in the ADI iterative method more often than the other one, i.e., relaxing the strict alternation requirement, in order to achieve a higher rate of convergence. Our analysis based on potential theory shows that this generalization of the ADI iterative method can give faster convergence than when strict alternation is required.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385695
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Towards a cost-effective ILU preconditioner with high level fill (1992)
    Springer
    BIT 32 (1992), S. 442-463 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 76S05 ; Minimum discarded fill (MDF) ; thresholdMDF ; minimum updating matrix ; matrix ordering ; preconditioned conjugate gradient
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract There has been increased interest in the effect of the ordering of the unknowns on Preconditioned Conjugate Gradient (PCG) methods. A recently proposed Minimum Discarded Fill (MDF) ordering technique is effective in finding goodILU(l) preconditioners, especially for problems arising from unstructured finite element grids. This algorithm can identify anisotropy in complicated physical structures and orders the unknowns in an appropriate direction. TheMDF technique may be viewed as an analogue of the minimum deficiency algorithm in sparse matrix technology, and hence is expensive to compute for high levelILU(l) preconditioners. In this work, several less expensive variants of theMDF technique are explored to produce cost-effectiveILU preconditioners. The ThresholdMDF ordering combinesMDF ideas with drop tolerance techniques to identify the sparsity pattern in theILU preconditioners. The Minimum Update Matrix (MUM) ordering technique is a simplification of theMDF ordering and is an analogue of the minimum degree algorithm. TheMUM ordering method is especially effective for large matrices arising from Navier-Stokes problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02074880
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Circulant preconditioners for second order hyperbolic equations (1992)
    Springer
    BIT 32 (1992), S. 650-664 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65N22 ; Hyperbolic equation ; circulant matrix ; condition number ; preconditioned conjugate gradient method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations in two dimensions are considered. We propose and analyze the use of circulant preconditioners for the solution of linear systems via preconditioned iterative methods such as the conjugate gradient method. Our motivation is to exploit the fast inversion of circulant systems with the Fast Fourier Transform (FFT). For second-order hyperbolic equations with initial and Dirichlet boundary conditions, we prove that the condition number of the preconditioned system is ofO(α) orO(m), where α is the quotient between the time and space steps andm is the number of interior gridpoints in each direction. The results are extended to parabolic equations. Numerical experiments also indicate that the preconditioned systems exhibit favorable clustering of eigenvalues that leads to a fast convergence rate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01994848
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Modified block-approximate factorization strategies (1992)
    Springer
    Numerische Mathematik 61 (1992), S. 91-110 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65F35 ; 65B99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Two variants of modified incomplete block-matrix factorization with additive correction are proposed for the iterative solution of large linear systems of equations. Both rigorous theoretical support and numerical evidence are given displaying their efficiency when applied to discrete second order partial differential equations (PDEs), even in the case of quasi-singular problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385499
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Convergence rate estimate for a domain decomposition method (1992)
    Springer
    Numerische Mathematik 61 (1992), S. 153-169 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We provide a convergence rate analysis for a variant of the domain decomposition method introduced by Gropp and Keyes for solving the algebraic equations that arise from finite element discretization of nonsymmetric and indefinite elliptic problems with Dirichlet boundary conditions in ℝ2. We show that the convergence rate of the preconditioned GMRES method is nearly optimal in the sense that the rate of convergence depends only logarithmically on the mesh size and the number of substructures, if the global coarse mesh is fine enough.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385503
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    An incomplete-factorization preconditioning using repeated red-black ordering (1992)
    Springer
    Numerische Mathematik 61 (1992), S. 433-454 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The convergence of the conjugate gradient method for the iterative solution of large systems of linear equations depends on proper preconditioning matrices. We present an efficient incomplete-factorization preconditioning based on a specific, “repeated red-black” ordering scheme and cyclic reduction. For the Dirichlet model problem, we prove that the condition number increases asymptotically slower with the number of equations than for usual incomplete factorization methods. Numerical results for symmetric and non-symmetric test problems and on locally refined grids demonstrate the performance of this method, especially for large linear systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385519
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    A breakdown-free Lanczos type algorithm for solving linear systems (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 29-38 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65F25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Lanczos type algorithms for solving systems of linear equations have their foundations in the theory of formal orthogonal polynomials and the method of moments which leads to a determinantal formula for their iterates. The various Lanczos type algorithms mainly differ by the way of computing the coefficients entering into the recurrence formulae. If the denominator in the formula for one of these coefficients is zero, then a breakdown occurs in the algorithm, and it must be stopped. Such a breakdown is in fact due to the non-existence of some orthogonal polynomial. In this paper we show how to jump over such a singularity by computing the next existing orthogonal polynomial by the block bordering method. The resulting algorithm, called MRZ, is equivalent to the nongeneric BIODIR algorithm (which is a look-ahead Lanczos type algorithm), but our derivation is much simpler.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385846
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    Galerkin-wavelet methods for two-point boundary value problems (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 123-144 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65N13 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Anti-derivatives of wavelets are used for the numerical solution of differential equations. Optimal error estimates are obtained in the applications to two-point boundary value problems of second order. The orthogonal property of the wavelets is used to construct efficient iterative methods for the solution of the resultant linear algebraic systems. Numerical examples are given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385851
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    A fast solver for the first biharmonic boundary value problem (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 297-313 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary This paper provides a fast and storage-saving method for the solution of the first biharmonic boundary value problem (b.v.p.). The b.v.p. is approximated via a special variational finite difference technique suggested earlier by V.G. Korneev. It is shown theoretically that our method produces an approximate solution to the finite difference equations inO(NlnNlnɛ−1) arithmetical operations, whereN is the number of unknowns and ɛ (0〈ɛ〈1) denotes the relative accuracy required. The numerical results obtained by our computer code CGMFC decisively substantiate the theoretical estimates given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385863
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    H-Splittings and two-stage iterative methods (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 345-356 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Convergence of two-stage iterative methods for the solution of linear systems is studied. Convergence of the non-stationary method is shown if the number of inner iterations becomes sufficiently large. TheR 1-factor of the two-stage method is related to the spectral radius of the iteration matrix of the outer splitting. Convergence is further studied for splittings ofH-matrices. These matrices are not necessarily monotone. Conditions on the splittings are given so that the two-stage method is convergent for any number of inner iterations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385865
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    On a class of matrices which arise in the numerical solution of Euler equations (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 411-431 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 15A48
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We study block matricesA=[Aij], where every blockA ij ∈ℂ k,k is Hermitian andA ii is positive definite. We call such a matrix a generalized H-matrix if its block comparison matrix is a generalized M-matrix. These matrices arise in the numerical solution of Euler equations in fluid flow computations and in the study of invariant tori of dynamical systems. We discuss properties of these matrices and we give some equivalent conditions for a matrix to be a generalized H-matrix.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385868
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Multilevel iterative methods for mixed finite element discretizations of elliptic problems (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 503-520 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385872
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Multilevel Schwarz methods (1992)
    Springer
    Numerische Mathematik 63 (1992), S. 521-539 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385873
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Optimal randomized parallel algorithms for computational geometry (1992)
    Springer
    Algorithmica 7 (1992), S. 91-117 
    Details
    ISSN: 1432-0541
    Keywords: Randomized ; Parallel algorithm ; Computational geometry ; Point location ; Triangulation ; Trapezoidal decomposition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present parallel algorithms for some fundamental problems in computational geometry which have a running time ofO(logn) usingn processors, with very high probability (approaching 1 asn → ∞). These include planar-point location, triangulation, and trapezoidal decomposition. We also present optimal algorithms for three-dimensional maxima and two-set dominance counting by an application of integer sorting. Most of these algorithms run on a CREW PRAM model and have optimal processor-time product which improve on the previously best-known algorithms of Atallah and Goodrich [5] for these problems. The crux of these algorithms is a useful data structure which emulates the plane-sweeping paradigm used for sequential algorithms. We extend some of the techniques used by Reischuk [26] and Reif and Valiant [25] for flashsort algorithm to perform divide and conquer in a plane very efficiently leading to the improved performance by our approach.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Optimal parallel algorithms for point-set and polygon problems (1992)
    Springer
    Algorithmica 7 (1992), S. 3-23 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Parallel algorithms ; Polygon ; All nearest-neighbor problem ; Kernel problem ; Convex hull
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758749
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers (1992)
    Springer
    Algorithmica 7 (1992), S. 51-75 
    Details
    ISSN: 1432-0541
    Keywords: Hypercube ; Parallel algorithms ; Convex hull ; Domination ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for both fine- and medium-grain hypercube computers, including a discussion of implementation, running times and results on an Intel iPSC hypercube, as well as theoretical results. For both serial and parallel computers, sorting plays an important role in geometric algorithms for determining simple properties, often being the dominant component of the running time. Since the time required to sort data on a hypercube computer is still not fully understood, the running times of some of our algorithms for unsorted data are not completely determined. For both the fine- and medium-grain models, we show that faster expected-case running time algorithms are possible for point sets generated randomly. Our algorithms are developed for sets of planar points, with several of them extending to sets of points in spaces of higher dimension.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758751
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    L 1 shortest paths among polygonal obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 55-88 
    Details
    ISSN: 1432-0541
    Keywords: Shortest paths ; Voronoi diagrams ; Rectilinear paths ; Wire routing ; Fixed orientation metrics ; Continuous Dijkstra algorithm ; Computational geometry ; Extremal graph theory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for computingL 1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nɛ−1/2 log2 n) time andO(nɛ−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL 1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758836
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    Line-segment intersection reporting in parallel (1992)
    Springer
    Algorithmica 8 (1992), S. 119-144 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Line-segment intersection reporting ; Segment tree ; PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give a parallel algorithm for line-segment intersection reporting in the plane. It runs in timeO(((n +k) logn log logn)/p) usingp processors on a concurrent-read-exclusive-write (CREW)-PRAM, wheren is the number of line segments,k is the number of intersections, andp ≤n +k.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758839
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    An efficient algorithm for one-step planar compliant motion planning with uncertainty (1992)
    Springer
    Algorithmica 8 (1992), S. 195-208 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Compliant motion ; Uncertainty ; Robotics ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Uncertainty in the execution of robot motion plans must be accounted for in the geometric computations from which plans are obtained, especially in the case where position sensing is inaccurate. We give anO(n 2 logn) algorithm to find a single commanded motion direction that will guarantee a successful motion in the plane from a specified start to a specified goal whenever such a one-step motion is possible. The plans account for uncertainty in the start position and in robot control, and anticipate that the robot may stick on or slide along obstacle surfaces with which it comes in contact. This bound improves on the best previous bound by a quadratic factor, and is achieved in part by a new analysis of the geometric complexity of the backprojection of the goal as a function of commanded motion direction.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758843
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs (1992)
    Springer
    Algorithmica 8 (1992), S. 177-194 
    Details
    ISSN: 1432-0541
    Keywords: Matching ; Computational geometry ; Bottleneck optimization problem ; Relative neighborhood graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E r k ) whereE r k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE r 17 . We also prove that ¦E r k ¦ 〈 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n 2) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n 1.5 log0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n 2 +n 1.5 log0.5 n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758842
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    On the parallel-decomposability of geometric problems (1992)
    Springer
    Algorithmica 8 (1992), S. 209-231 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Mesh-connected arrays of processors ; Parallel algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d ) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen 〉p. The goal we seek is to achieve, when solving a problem of sizen 〉p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen 〉p as when solving a problem of sizep.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758844
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Output-sensitive generation of the perspective view of isothetic parallelepipeds (1992)
    Springer
    Algorithmica 8 (1992), S. 257-283 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Hidden-line elimination ; Perspective view ; Isothetic rectangles ; Parallelepipeds ; Fractional cascading ; Segment tree ; Range tree ; Dominance relation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present a new hidden-line elemination technique for displaying the perspective view of a scene of three-dimensional isothetic parallelepipeds (3D-rectangles). We assume that the 3D-rectangles are totally ordered based upon the dominance relation of occlusion. The perspective view is generated incrementally, starting with the closest 3D-rectangle and proceeding away from the view point. Our algorithm is scene-sensitive and uses0((n +d) logn log logn) time, wheren is the number of 3D-rectangles andd is the number of edges of the display. This improves over the heretofore best known technique. The primary data structure is an efficient alternative to dynamic fractional cascading for use with augmented segment and range trees when the universe is fixed beforehand. It supports queries inO((logn +k) log logn) time, wherek is the size of the response, and insertions and deletions inO(logn log logn) time, all in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758847
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Probing a scene of nonconvex polyhedra (1992)
    Springer
    Algorithmica 8 (1992), S. 321-342 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Geometric probing ; Polyhedral scenes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show, in this paper, how the exact shapes of a class of polyhedral scenes can be computed by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces, and such that no edge is contained in the supporting plane of a nonincident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows us to compute the exact shape of a simple polygon with no collinear edges by means of at most3n — 3 probes, wheren is the number of edges of the polygon. This is optimal in the worst case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists ofk polyhedra with altogethern faces andm edges, we show that $$\tfrac{{10}}{3}n\left( {m + k} \right) - 2m - 3k$$ probes are sufficient to compute the exact shapes of the polyhedra.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758849
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Quasi-optimal upper bounds for simplex range searching and new zone theorems (1992)
    Springer
    Algorithmica 8 (1992), S. 407-429 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Range searching ; Space-time tradeoff
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents quasi-optimal upper bounds for simplex range searching. The problem is to preprocess a setP ofn points in ℜd so that, given any query simplexq, the points inP ∩q can be counted or reported efficiently. Ifm units of storage are available (n 〈m 〈n d ), then we show that it is possible to answer any query inO(n 1+ɛ/m 1/d ) query time afterO(m 1+ɛ) preprocessing. This bound, which holds on a RAM or a pointer machine, is almost tight. We also show how to achieveO(logn) query time at the expense ofO(n d+ɛ) storage for any fixed ɛ 〉 0. To fine-tune our results in the reporting case we also establish new zone theorems for arrangements and merged arrangements of planes in 3-space, which are of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758854
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Simultaneous inner and outer approximation of shapes (1992)
    Springer
    Algorithmica 8 (1992), S. 365-389 
    Details
    ISSN: 1432-0541
    Keywords: Polygonal approximation ; Algorithmic paradigms ; Shape approximation ; Computational geometry ; Implicit complexity parameters ; Banach-Mazur metric
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer 〉 0,s 〉 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... 〈-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)〈-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Approximate motion planning and the complexity of the boundary of the union of simple geometric figures (1992)
    Springer
    Algorithmica 8 (1992), S. 391-406 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Motion planning ; Boundary complexity ; Combinatorial geometry ; Analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have a running time of Ω(n 2), wheren is the number of obstacle corners. We introduce thetightness of a motion-planning problem as a measure of the difficulty of a planning problem in an intuitive sense and describe an algorithm with a running time ofO((a/b · 1/ɛcrit + 1)n(logn)2), wherea ≥b are the lengths of the sides of a rectangle and ɛcrit is the tightness of the problem. We show further that the complexity (= number of vertices) of the boundary ofn bow ties (see Figure 1) isO(n). Similar results for the union of other simple geometric figures such as triangles and wedges are also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758853
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Minimum-link paths among obstacles in the plane (1992)
    Springer
    Algorithmica 8 (1992), S. 431-459 
    Details
    ISSN: 1432-0541
    Keywords: Link distance ; Shortest paths ; Motion planning ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eα(n) log2 n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and α(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758855
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    Electronic Resource
    Electronic Resource
    Parallel methods for visibility and shortest-path problems in simple polygons (1992)
    Springer
    Algorithmica 8 (1992), S. 461-486 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Data structures ; Visibility ; Polygons ; CREW PRAM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we give efficient parallel algorithms for solving a number of visibility and shortest-path problems for simple polygons. Our algorithms all run inO(logn) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygonP, which we call thestratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility ofP from an edge, constructing the visibility graph of the vertices ofP (using an output-sensitive number of processors), constructing the shortest-path tree from a vertex ofP, and determining all-farthest neighbors for the vertices inP. The computational model we use is the CREW PRAM.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    On a hierarchical basis multilevel method with nonconforming P1 elements (1992)
    Springer
    Numerische Mathematik 62 (1992), S. 189-212 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65F35 ; 65N20 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We develop a hierarchical basis multilevel method for symmetric second order elliptic boundary value problems in two-dimensional polygonal domains based on nonconforming P1 triangular elements. The main result is that the condition number of the hierarchical discretization is bounded byO(k) wherek is the number of refinement levels. For comparison, Yserentant's result yields the sharp boundO(k 2) for the corresponding hierarchical discretization with conforming linear elements.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01396226
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    Convergence of sequential and asynchronous nonlinear paracontractions (1992)
    Springer
    Numerische Mathematik 62 (1992), S. 305-319 
    Details
    ISSN: 0945-3245
    Keywords: MSC 1991 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We establish the convergence of sequential and asynchronous iteration schemes for nonlinear paracontracting operators acting in finite dimensional spaces. Applications to the solution of linear systems of equations with convex constraints are outlined. A first generalization of one of our convergence results to an infinite pool of asymptotically paracontracting operators is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01396232
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Some vector sequence transformations with applications to systems of equations (1992)
    Springer
    Numerical algorithms 3 (1992), S. 75-80 
    Details
    ISSN: 1572-9265
    Keywords: AMS (MOS) 65B05 ; 65F10 ; 65F25 ; Vector sequence ; extrapolation ; Lanczos method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract First, recursive algorithms for implementing some vector sequence transformations are given. In a particular case, these transformations are generalizations of Shanks transformation and the G-transformation. When the sequence of vectors under transformation is generated by linear fixed point iterations, Lanczos' method and the CGS are recovered respectively. In the case of a sequence generated by nonlinear fixed point iterations, a quadratically convergent method based on the ε-algorithm is recovered and a nonlinear analog of the CGS method is obtained.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02141917
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    A tight upper bound for the number of intersections between two rectangular paths (1991)
    Springer
    BIT 31 (1991), S. 598-606 
    Details
    ISSN: 1572-9125
    Keywords: B.7.1 ; B.7.2 ; F.2.2 ; G.2.2 ; Computational geometry ; interference ; intersection ; rectangular path ; upper bound ; VLSI layout
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The problem of finding the number of intersections between two geometric figures in the plane has been studied extensively in literature. In this paper, the geometric figure comprising a continuous rectilinear path (called rectangular path) is considered, and a tight (least) upper bound onI(P, Q), the number of intersections between two rectangular pathsP andQ, is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01933175
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    Probabilistic analysis of an algorithm for solving thek-dimensional all-nearest-neighbors problem by projection (1991)
    Springer
    BIT 31 (1991), S. 558-565 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; Computational geometry ; plane-sweep algorithm ; proximity problems ; all-nearest-neighbor problem ; probabilistic analysis of algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A well-known simple heuristic algorithm for solving the all-nearest-neighbors problem in thek-dimensional Euclidean spaceE k ,k〉1, projects the given point setS onto thex-axis. For each pointq εS a nearest neighbor inS under anyL p -metric (1 ≤p ≤ ∞) is found by sweeping fromq into two opposite directions along thex-axis. If δ q denotes the distance betweenq and its nearest neighbor inS the sweep process stops after all points in a vertical 2δ q -slice centered aroundq have been examined. We show that this algorithm solves the all-nearest-neighbors problem forn independent and uniformly distributed points in the unit cube [0,1] k in Θ(n 2−1/k ) expected time, while its worst-case performance is Θ(n 2).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01933171
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems (1991)
    Springer
    BIT 31 (1991), S. 632-646 
    Details
    ISSN: 1572-9125
    Keywords: 65F10 ; 65F15 ; Skew-Hermitian type Toeplitz matrix ; circulant matrix ; skew-circulant matrix ; preconditioned conjugate gradient method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We study the solutions of Toeplitz systemsA n x=b by the preconditioned conjugate gradient method. Then ×n matrixA n is of the forma 0 I+H n wherea 0 is a real number,I is the identity matrix andH n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC n and the skew-circulant matrixS n whereA n =1/2(C n +S n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC −1 n An andS −1 n A n . For Toeplitz matricesA n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC n andS n and prove that the singular values ofC −1 n A n andS −1 n A n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01933178
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    Finding minimal nested polygons (1991)
    Springer
    BIT 31 (1991), S. 230-236 
    Details
    ISSN: 1572-9125
    Keywords: F.1.2 ; Algorithm ; Complexity ; Computational geometry ; Minimal nested polygon
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n 2) algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01931283
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    Local refinement techniques for elliptic problems on cell-centered grids (1991)
    Springer
    Numerische Mathematik 59 (1991), S. 431-452 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N20 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v〉1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385790
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    A posteriori error estimators for the Stokes equations II non-conforming discretizations (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 235-249 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N22 ; 76D05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We present an a posteriori error estimator for the non-conforming Crouzeix-Raviart discretization of the Stokes equations which is based on the local evaluation of residuals with respect to the strong form of the differential equation. The error estimator yields global upper and local lower bounds for the error of the finite element solution. It can easily be generalized to the stationary, incompressible Navier-Stokes equations and to other non-conforming finite element methods. Numerical examples show the efficiency of the proposed error estimator.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385723
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    A domain decomposition algorithm for elliptic problems in three dimensions (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 219-234 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N30
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary Most domain decomposition algorithms have been developed for problems in two dimensions. One reason for this is the difficulty in devising a satisfactory, easy-to-implement, robust method of providing global communication of information for problems in three dimensions. Several methods that work well in two dimension do not perform satisfactorily in three dimensions. A new iterative substructuring algorithm for three dimensions is proposed. It is shown that the condition number of the resulting preconditioned problem is bounded independently of the number of subdomains and that the growth is quadratic in the logarithm of the number of degrees of freedom associated with a subdomain. The condition number is also bounded independently of the jumps in the coefficients of the differential equation between subdomains. The new algorithm also has more potential parallelism than the iterative substructuring methods previously proposed for problems in three dimensions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385722
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    Numerical stability of the cyclic Richardson iteration (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 251-290 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The success of the cyclic Richardson iteration depends on the proper ordering of the acceleration parameters. We give a rigorous error analysis to show that, with the proper ordering, the relative error in the iterative method, when properly terminated, is not larger than the error incurred in stable direct methods such as Cholesky factorization. For both the computed approximation $$\tilde u$$ tou=L −1f satisfies $$\left\| {u - \tilde u} \right\|$$ ≦ cond (L)‖u‖2−t and this bound is attainable. We also show that the residual norm $$\left\| {f - L\tilde u} \right\|$$ is bounded by ‖L‖ cond $$(L)\left\| {\tilde u} \right\|2^{ - t} $$ . This bound is attainable for a small cycle lengthN. Our analysis suggests that for a larger cycle lengthN the residuals are bounded by $$\sqrt {cond(L)} \left\| L \right\|\left\| {\tilde u} \right\|2^{ - t} $$ . We construct a theoretical example in which this bound is attainable. However we observed in all numerical tests that ultimately the residual norms were of order $$\left\| L \right\|\left\| {\tilde u} \right\|2^{ - t} $$ . We explain why in practice even the factor $$\sqrt {cond(L)} $$ is never encountered. Therefore the residual stopping criterion for the Richardson iteration appears to be very reliable and the method itself appears to be stable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385724
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    QMR: a quasi-minimal residual method for non-Hermitian linear systems (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 315-339 
    Details
    ISSN: 0945-3245
    Keywords: 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The biconjugate gradient (BCG) method is the “natural” generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. In this paper, we present a novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the nonsymmetric Lanczos algorithm is proposed. It is shown how BCG iterates can be recovered stably from the QMR process. Some further properties of the QMR approach are given and an error bound is presented. Finally, numerical experiments are reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385726
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    Accelerated Landweber iterations for the solution of ill-posed equations (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 341-373 
    Details
    ISSN: 0945-3245
    Keywords: 65J10 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept. If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy. To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage. Numerical examples are given including a comparison to the method of conjugate gradients.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385727
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    An alternating direction implicit method for orthogonal spline collocation linear systems (1991)
    Springer
    Numerische Mathematik 59 (1991), S. 413-429 
    Details
    ISSN: 0945-3245
    Keywords: 65N35 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary An Alternating Direction Implicit method is analyzed for the solution of linear systems arising in high-order, tensor-product orthogonal spline collocation applied to some separable, second order, linear, elliptic partial differential equations in rectangles. On anNxN partition, with Jordan's selection of the acceleration parameters, the method requiresO(N 2 ln 2 N) arithmetic operations to produce an approximation whose accuracy, in theH 1-norm, is that of the collocation solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385789
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Convergence of block iterative methods for linear systems arising in the numerical solution of Euler equations (1991)
    Springer
    Numerische Mathematik 59 (1991), S. 541-559 
    Details
    ISSN: 0945-3245
    Keywords: 65F10 ; 65N22 ; 15A48
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We discuss block matrices of the formA=[A ij ], whereA ij is ak×k symmetric matrix,A ij is positive definite andA ij is negative semidefinite. These matrices are natural block-generalizations of Z-matrices and M-matrices. Matrices of this type arise in the numerical solution of Euler equations in fluid flow computations. We discuss properties of these matrices, in particular we prove convergence of block iterative methods for linear systems with such system matrices.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385795
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Additive Schwarz algorithms for parabolic convection-diffusion equations (1991)
    Springer
    Numerische Mathematik 60 (1991), S. 41-61 
    Details
    ISSN: 0945-3245
    Keywords: 65N30 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary In this paper, we consider the solution of linear systems of algebraic equations that arise from parabolic finite element problems. We introduce three additive Schwarz type domain decomposition methods for general, not necessarily selfadjoint, linear, second order, parabolic partial differential equations and also study the convergence rates of these algorithms. The resulting preconditioned linear system of equations is solved by the generalized minimal residual method. Numerical results are also reported.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385713
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Moving a disc between polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 182-191 
    Details
    ISSN: 1432-0541
    Keywords: Motion planning ; Polygonal obstacles ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An algorithm is given for finding a collision-free path for a disc between a collection of polygons havingn corners in total. The polygons are fixed and can be preprocessed. A query specifies the radiusr of the disc to be moved and the start and destination points of the center of the disc. The answer whether a feasible path exists is given in timeO(logn). Returning a feasible path is done in additional time proportional to the length of the description of the path. Preprocessing time isO(n logn) and space complexity isO(n).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759040
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    AnO(n logn) plane-sweep algorithm forL 1 andL ∞ Delaunay triangulations (1991)
    Springer
    Algorithmica 6 (1991), S. 207-221 
    Details
    ISSN: 1432-0541
    Keywords: Delaunay triangulation ; Plane-sweep algorithm ; Voronoi diagram ; L 1 metric ; L ∞ metric ; Computational geometry ; Minimal spanning tree
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract TheDelaunay diagram on a set of points in the plane, calledsites, is the straight-line dual graph of the Voronoi diagram. When no degeneracies are present, the Delaunay diagram is a triangulation of the sites, called theDelaunay triangulation. When degeneracies are present, edges must be added to the Delaunay diagram to obtain a Delaunay triangulation. In this paper we describe an optimalO(n logn) plane-sweep algorithm for computing a Delaunay triangulation on a possibly degenerate set of sites in the plane under theL 1 metric or theL ∞ metric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759042
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    Order-k voronoi diagrams of sites with additive weights in the plane (1991)
    Springer
    Algorithmica 6 (1991), S. 490-521 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Voronoi diagrams ; Geömetric transformation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract It is shown that the order-k Voronoi diagram of n sites with additive weights in the plane has at most (4k−2)(n−k) vertices, (6k−3)(n−k) edges, and (2k−1)(n−itk) + 1 regions. These bounds are approximately the same as the ones known for unweighted order-k Voronoi diagrams. Furthermore, tight upper bounds on the number of edges and vertices are given for the case that every weighted site has a nonempty region in the order-1 diagram. The proof is based on a new algorithm for the construction of these diagrams which generalizes a plane-sweep algorithm for order-1 diagrams developed by Steven Fortune. The new algorithm has time-complexityO(k 2 n logn) and space-complexityO(kn). It is the only nontrivial algorithm known for constructing order-kc Voronoi diagrams of sites withadditive weights. It is fairly simple and of practical interest also in the special case of unweighted sites.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759056
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Convex hulls of objects bounded by algebraic curves (1991)
    Springer
    Algorithmica 6 (1991), S. 533-553 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms and data structures ; Algebraic geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an0(n ·d o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759058
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Finding a minimal cover for binary images: An optimal parallel algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 624-657 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Image compression ; Minimal square covers ; Orthogonal polygons ; Parallel prefix computations ; Minimal vertex covers ; Bipartite graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a black-and-white image, represented by an array of √n × √n binary-valued pixels, we wish to cover the black pixels with aminimal set of (possibly overlapping) maximal squares. It was recently shown that obtaining aminimum square cover for a polygonal binary image with holes is NP-hard. We derive an optimal parallel algorithm for theminimal square cover problem, which for any desired computation timeT in [logn,n] runs on an EREW-PRAM with (n/T) processors. The cornerstone of our algorithm is a novel data structure, the cover graph, which compactly represents the covering relationships between the maximal squares of the image. The size of the cover graph is linear in the number of pixels. This algorithm has applications to problems in VLSI mask generation, incremental update of raster displays, and image compression.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759065
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    On partitioning rectilinear polygons into star-shaped polygons (1991)
    Springer
    Algorithmica 6 (1991), S. 771-800 
    Details
    ISSN: 1432-0541
    Keywords: Polygon decomposition ; Star-shaped polygons ; Computational geometry
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759071
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Computational geometry algorithms for the systolic screen (1991)
    Springer
    Algorithmica 6 (1991), S. 734-761 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Clustering ; Convex hull ; Digitized pictures ; Hulls ; Maxima ; Mesh-of-processors ; Parallel computing ; Separability ; Systolic array ; Visibility ; Voronoi diagram
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Adigitized plane Π of sizeM is a rectangular √M × √M array of integer lattice points called pixels. A √M × √M mesh-of-processors in which each processorP ij represents pixel (i,j) is a natural architecture to store and manipulate images in Π; such a parallel architecture is called asystolic screen. In this paper we consider a variety of computational-geometry problems on images in a digitized plane, and present optimal algorithms for solving these problems on a systolic screen. In particular, we presentO(√M)-time algorithms for determining all contours of an image; constructing all rectilinear convex hulls of an image (peeling); solving the parallel and perspective visibility problem forn disjoint digitized images; and constructing the Voronoi diagram ofn planar objects represented by disjoint images, for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., allL p metrics). These algorithms implyO(√M)-time solutions to a number of other geometric problems: e.g., rectangular visibility, separability, detection of pseudo-star-shapedness, and optical clustering. One of the proposed techniques also leads to a new parallel algorithm for determining all longest common subsequences of two words.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759069
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    Adaptive Lanczos methods for recursive condition estimation (1991)
    Springer
    Numerical algorithms 1 (1991), S. 1-19 
    Details
    ISSN: 1572-9265
    Keywords: AMS(MOS) ; 15A18 ; 65F10 ; 65F20 ; 65F35 ; Adaptive methods ; condition estimation ; control ; downdating ; eigenvalues ; Lanczos methods ; matrix modifications ; recursive least squares ; signal processing ; singular values ; updating
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02145580
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Block elimination with one refinement solves bordered linear systems accurately (1990)
    Springer
    BIT 30 (1990), S. 490-507 
    Details
    ISSN: 1572-9125
    Keywords: 15A06 ; 65F05 ; 65F10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Linear systems with a fairly well-conditioned matrixM of the form $$\begin{array}{*{20}c} n \\ 1 \\ \end{array} \mathop {\left( {\begin{array}{*{20}c} A & b \\ c & d \\ \end{array} } \right)}\limits^{\begin{array}{*{20}c} n & 1 \\ \end{array} } $$ , for which a ‘black box’ solver forA is available, can be accurately solved by the standard process of Block Elimination, followed by just one step of Iterative Refinement, no matter how singularA may be — provided the ‘black box’ has a property that is possessed by LU- and QR-based solvers with very high probability. The resulting Algorithm BE + 1 is simpler and slightly faster than T.F. Chan's Deflation Method, and just as accurate. We analyse the case where the ‘black box’ is a solver not forA but for a matrix close toA. This is of interest for numerical continuation methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01931663
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    A divide-and-conquer algorithm for constructing relative neighborhood graph (1990)
    Springer
    BIT 30 (1990), S. 196-206 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; Computational geometry ; Divide-and-Conquer algorithm ; Relative Neighborhood Graph
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract AnO(n logn) divide-and-conquer algorithm for finding the relative neighborhood graph RNG(V) of a set V ofn points in Euclidean space is presented. If implemented in parallel, its time complexity isO(n) and it requiresO(logn) processors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02017341
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    A multidomain spectral collocation method for the Stokes problem (1990)
    Springer
    Numerische Mathematik 58 (1990), S. 441-464 
    Details
    ISSN: 0945-3245
    Keywords: AMS(MOS): 65P30 ; 65N35 ; 65F10 ; CR: G1.8
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We propose a multidomain spectral collocation scheme for the approximation of the two-dimensional Stokes problem. We show that the discrete velocity vector field is exactly divergence-free and we prove error estimates both for the velocity and the pressure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385635
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Two preconditioners based on the multi-level splitting of finite element spaces (1990)
    Springer
    Numerische Mathematik 58 (1990), S. 163-184 
    Details
    ISSN: 0945-3245
    Keywords: AMS(MOS) ; 65F10 ; 65F35 ; 65N20 ; 65N30 ; CR: G 1.8
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The hierarchical basis preconditioner and the recent preconditioner of Bramble, Pasciak and Xu are derived and analyzed within a joint framework. This discussion elucidates the close relationship between both methods. Special care is devoted to highly nonuniform meshes; exclusively local properties like the shape regularity of the finite elements are utilized.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385617
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    The conditioning of the stiffness matrix for certain elements approximating the incompressibility condition in fluid dynamics (1990)
    Springer
    Numerische Mathematik 58 (1990), S. 203-214 
    Details
    ISSN: 0945-3245
    Keywords: AMS(MOS) ; 65F10 ; 65N30 ; 76D05 ; CR: G1.8
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary In order to solve the Stokes equations numerically, Crouzeix and Raviart introduced elements satisfying a discrete divergence condition. For the two dimensional case and uniform triangulations it is shown, that using the standard basis functions, the conditioning of the stiffness matrix is of orderN 2, whereN is the dimension of the corresponding finite element space. Hierarchical bases are introduced which give a condition number of orderN log(N)3.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01385619
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    A new algorithm for the largest empty rectangle problem (1990)
    Springer
    Algorithmica 5 (1990), S. 65-73 
    Details
    ISSN: 1432-0541
    Keywords: Computational geometry ; Algorithms ; Computational complexity ; Largest empty rectangle problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A rectangleA and a setS ofn points inA are given. We present a new simple algorithm for the so-called largest empty rectangle problem, i.e., the problem of finding a maximum area rectangle contained inA and not containing any point ofS in its interior. The computational complexity of the presented algorithm isO(n logn + s), where s is the number of possible restricted rectangles considered. Moreover, the expected performance isO(n · logn).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840377
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Parallel geometric algorithms on a mesh-connected computer (1990)
    Springer
    Algorithmica 5 (1990), S. 155-177 
    Details
    ISSN: 1432-0541
    Keywords: Parallel algorithms ; Computational geometry ; Mesh-connected computer ; Multipoint location ; Voronoi diagrams
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a number of geometric problems can be solved on a √n × √n mesh-connected computer (MCC) inO(√n) time, which is optimal to within a constant factor, since a nontrivial data movement on an MCC requires Ω(√n) time. The problems studied here include multipoint location, planar point location, trapezoidal decomposition, intersection detection, intersection of two convex polygons, Voronoi diagram, the largest empty circle, the smallest enclosing circle, etc. TheO(√n) algorithms for all of the above problems are based on the classical divide-and-conquer problem-solving strategy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01840383
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...