𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Time–Space Complexity of Geometric Elimination Procedures

✍ Scribed by Joos Heintz; Guillermo Matera; Ariel Waissbein

Publisher
Springer
Year
2001
Tongue
English
Weight
424 KB
Volume
11
Category
Article
ISSN
0938-1279

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Dataflow Time and Space Complexity o
The Dataflow Time and Space Complexity of FFTs
✍ A.P.W. Bohm; R.E. Hiromoto 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 747 KB

In this paper we analyze the performance of a recursive and an iterative fast Fourier transform algorithm, written in Id and run on MINT, a simulator for the Monsoon dataflow machine. Our complexity measures are: the number of instructions executed, the critical path length of the dataflow graph, an

Impact of communications on the complexi
Impact of communications on the complexity of the Parallel Gaussian Elimination
✍ E. Bampis; J.C. Konig; D. Trystram 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 275 KB

This paper presents an extension to the complexity analysis of parallel algorithms on MIMD computers with a shared-memory system which takes into account communications. This analysis shows that the well-known asymptotically optimal results are insufficient because we show that the overhead is in O(

On the complexity of some geometric prob
On the complexity of some geometric problems in unbounded dimension
✍ Nimrod Megiddo 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 429 KB

This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit ball% and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven no