178 research outputs found
Robust Proximity Queries: An Illustration of Degree-driven Algorithms Design
No full textIn the context of methodologies intended to confer robustness to geometric algorithms,
we elaborate on the exact-computation paradigm and formalize the notion of degree of a
geometric algorithm as a worst-case quantification of the precision (number of bits) to which arithmetic
calculation have to be executed in order to guarantee topological correctness. We also propose
a formalism for the expeditious evaluation of algorithmic degree. As an application of this paradigm
and an illustration of our general approach where algorithm design is driven also by the degree,
we consider the important classical problem of proximity queries in two and three dimensions and
develop a new technique for the efficient and robust execution of such queries based on an implicit
representation of Voronoi diagrams. Our new technique offers both low degree and fast query time
and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number
of operations, and arithmetic degree
The role of arithmetic in fast parallel matrix inversion
No full textn the last two decades several NC algorithms for solving basic linear algebraic problems have appeared in the literature. This interest was clearly motivated by the emergence of a parallel computing technology and by the wide applicability of matrix computations. The traditionally adopted computation model, however, ignores the arithmetic aspects of the applications, and no analysis is currently available demonstrating the concrete feasibility of many of the known fast methods. In this paper we give strong evidence to the contrary, on the sole basis of the issue of robustness, indicating that some theoretically brilliant solutions fail the severe test of the ``Engineering of Algorithms.'' We perform a comparative analysis of several well-known numerical matrix inversion algorithms under both fixed- and variable-precision models of arithmetic. We show that, for most methods investigated, a typical input leads to poor numerical performance, and that in the exact-arithmetic setting no benefit derives from conditions usually deemed favorable in standard scientific computing. Under these circumstances, the only algorithm admitting sufficiently accurate NC implementations is Newton's iterative method, and the word size required to guarantee worst-case correctness appears to be the critical complexity measure. Our analysis also accounts for the observed instability of the considered superfast methods when implemented with the same floating-point arithmetic that is perfectly adequate for the fixed-precision approach
A practical constructive scheme for deterministic shared-memory access
No full textWe present an explicit memory organization scheme for ditributing M data items among N memory modules where M=Theta(N^(1.5-O(1/log N))). Each datum is replicated into a constant number of copies assigned to distinct modules. Assuming that N processors are connected to the memories through a complete graph, we provide an access protocol so that the processors can read/write any set of N' <= N distinct data in O((N')^(1/3)log*N'+logN) worst-case time. The address computation can be carried out efficiently without resort to a complete memory map and using O(1) internal registers per processor
Checking the Convexity of Polytopes and the Planarity of Subdivisions
No full textThis paper studies the problem of verifying the correctness of geometric structures. We design optimal checkers for convex polytopes in two and higher dimensions, and for various types of planar subdivisions, such as triangulations, Delaunay triangulations, and convex subdivisions. Our checkers are simpler and more general than the ones previously described in the literature. Their performance is studied also in terms of the degree, which characterizes the arithmetic precision required
An O(√n)-worst-case-time solution to the granularity problem
No full textIn this paper we deal with the granularity problem, that is, the problem of implementing a shared memory in a distributed system where n processors are connected to n memory modules through a complete network (Module Parallel Computer). We present a memory organization scheme where m=O(n^2) variables, each replicated into a 2c — 1 copies (for constant c), are evenly distributed among the n modules, so that a suitable access protocol allows any set of at most n distinct read/write operations to be performed by the processors in O(sqrt(n)) parallel steps in the worst case. The well known strategy based on multiple copies is needed to avoid the worst-case O(n)-time, since only a majority of the copies of each variable need be accessed for any operation. The memory organization scheme can be extended to deal with m=O(n^3) variables attaining an O(n^(2/3))-time complexity in the worst case
A simple explanation of hyperon polarization at high pt
No full textWe present the first truly dynamical calculation of the single transverse-spin asymmetry for the process pN --> B(up) + X, where B is LAMBDA0 or SIGMA0,+/- observed at large angles. After showing that the trip le-Regge model gives a good representation of the inclusive unpolarized cross sections, the polarization is calculated by considering the hyperon to emerge in the final state either directly or as the result of virtual dissociation of a parent baryon. Our results reproduce very well both the measured p(T) and x(F) dependence of the hyperon polarization
A generalization of the binary Preparata code
No full textAbstractA classical binary Preparata code P2(m) is a nonlinear (2m+1,22(2m-1-m),6)-code, where m is odd. It has a linear representation over the ring Z4 [Hammons et al., The Z4-linearity of Kerdock, Preparata, Goethals and related codes, IEEE Trans. Inform. Theory 40(2) (1994) 301–319]. Here for any q=2l>2 and any m such that (m,q-1)=1 a nonlinear code Pq(m) over the field F=GF(q) with parameters (q(Δ+1),q2(Δ-m),d⩾3q), where Δ=(qm-1)/(q-1), is constructed. If d=3q this set of parameters generalizes that of P2(m). The equality d=3q is established in the following cases: (1) for a series of initial admissible values q and m such that qm<2100; (2) for m=3,4 and any admissible q, and (3) for admissible q and m such that there exists a number m1 with m1|m and d(Pq(m1))=3q. We apply the approach of [Nechaev and Kuzmin, Linearly presentable codes, Proceedings of the 1996 IEEE International Symposium Information Theory and Application Victoria, BC, Canada 1996, pp. 31–34] the code P is a Reed–Solomon representation of a linear over the Galois ring R=GR(q2,4) code P dual to a linear code K with parameters near to those of generalized linear Kerdock code over R
Parallel algorithms for convex hulls and proximity problems
No full textComputational geometry is concerned with the algorithmic aspects of solving geometric problems. The problems are motivated from and have application to such diverse areas as computer graphics, robotics, computer vision, and operations research. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for some basic geometric problems. The model of parallel computation used in our studies is the Parallel Random Access Machine (CREW PRAM).Constructing the convex hull of a set of n points in \Re\sp3 is one of the most studied problems in computational geometry. It is known that any parallel algorithm for this problem requires time, and must perform work (i.e., the product of the time and the number of processors used by the algorithm). Despite the long held attention of many researchers, until recently no time or work optimal parallel algorithm was known for the three-dimensional convex hull problem. We establish a criterion that can be used for constructing the merged hull of two disjoint subhulls, which forms the basis of an O(\log\sp2 n) time and O(n) processor convex hull algorithm. Development of such a criterion had proven to be problematical in previous algorithms. Next, we show that the three-dimensional convex hull problem can be solved in time using O(n\sp{1+\alpha}) processors, for any constant 0 1, by substituting many-way divide-and-conquer for the traditional two-way divide-and-conquer paradigm; this is the first time-optimal parallel algorithm for this problem.Another important class of geometric problems is concerned with answering proximity queries about geometric objects. Let P and Q be simple polygons. Vertices and are visible if does not properly intersect P or Q. The proximity problems considered in this thesis are: (i) finding a closest pair of boundary points between P and Q, and (ii) finding a closest pair of visible vertices between P and Q. For both problems, we give algorithms that run in time (which is known to be optimal) using O(n) processors. For the first problem, the complexity of the best previous parallel algorithm was O(\log\sp2 n) time using O(n) processors, and for the latter problem, no prior parallel algorithm was known. Serial versions of our parallel algorithms can be implemented in time. For problems of the first type, the complexity of the best previous sequential algorithm was , and for problems of the second type, our sequential algorithm is simpler than all previous algorithms.Made available in DSpace on 2011-05-07T13:21:18Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9522076.pdf: 4511935 bytes, checksum: 2a70dd2c8c871a0d3182630025a684c8 (MD5)
Previous issue date: 1995Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T14:53:40Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:24:51-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionRemoved middle name to match other item deposits.
Metadata cleaned/updated by [email protected] 2015-5-13.ETDs are only available to UIUC Users without author permissionU of I Onl
- …
