| 1. |
- Fjällström, Per-Olof
(författare)
-
Algorithms for Graph Partitioning: A Survey
- 1998
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The graph partitioning problem is as follows. Given a graph G = (N, E) (where N is a set of weighted nodes and E is a set of weighted edges) and a positive integer p , find p subsets N1 , N2 ,... Np of N such thatthe union set of Ni where i = 1...p equals N and Ni is disjoint from Nj for i =/ j , W(i)~W/p where i = 1, 2...p , where W(i) and W are the sums of the node weights in Ni and N , respectively,the cut size, i.e., the sum of the weights of edges crossing between subsets is minimized.This problem is of interest in areas such as VLSI placement and routing, and efficient parallel implementations of finte element methods. In this survey we summarize the state-of-the-art of sequential and parallel graph partitioning problems.
|
|
| 2. |
- Fjällström, Per-Olof
(författare)
-
Batched Range Searching on a Mesh-Connected SIMD Computer
- 1997
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Given a set of n points and hyperrectangles in a d-dimensional space, the batched range-searching problem is to determine which points each hyperrectangle contains. We present two parallel algorithms for this problem on a √(n) * √(n) mesh-connected parallel computer: one average-case efficient algorithm based on cell division, and one worst-case efficient divide-and-conquer algorithm. Besides the asymptotic analysis of their running times, we present an experimental evaluation of the algorithms.
|
|
| 3. |
- Fjällström, Per-Olof, 1954-, et al.
(författare)
-
Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering
- 1998
-
Ingår i: International Journal of Computational Geometry & Applications. - : World Scientific Publishing Co. Pte. Ltd.. - 0218-1959. ; 8:1, s. 67-83
-
Tidskriftsartikel (refereegranskat)abstract
- Contact searching is an important and time-consuming part of computer simulation of certain deformation processes. Contact searching can be facilitated by orthogonal range searching. We have experimentally evaluated four methods for orthogonal range searching: the projection method, the cell method, the k-d tree method, and the range tree method. The results of our experiments indicate that two of these methods, the cell and k-d tree methods, have practical significance. The cell method is in most cases faster than the k-d tree method.
|
|
| 4. |
- Fjällström, Per-Olof
(författare)
-
Parallel Algorithms for Batched Range Searching on Coarse-Grained Multicomputers
- 1997
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We defne the batched range-searching problem as follows: given a set S of n points and a set Q of m hyperrectangles, report for each hyperrect; angle which points it contains. This problem has applications in, for ex ample, computer-aided design and engineering. We present several parallel algorithms for this problem on coarse-grained multicomputers. Our algorithms are based on well-known average- and worst-case effcient sequential algorithms. One of our algorithms solves the d-dimensional batched range-searching problem in O(Ts(n logd-1p,p) + Ts(m logd-1p,p) + ((m +n)logd-1(n/p) + m logd-1p log(n/p) + k)/p) time on a p-processor coarse-grained multicomputer. (Ts(n,p) denotes the time globally to sort n numbers on a p-processor multicomputer, and k is the total number of reported points.
|
|
| 5. |
- Fjällström, Per-Olof
(författare)
-
Parallel Algorithms for Searching Monotone Matrices on Coarse Grained Multicomputers
- 1998
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We present parallel algorithms for geometric problems on coarse grained multicomputers. More specifically, for a square mesh-connected p-processor computer, we show that:The implicit row maxima problem on a totally monotone n × n matrix can be solved in O((n/p) log p) time, if n > p2 .The all-farthest-neighbors problem for a convex n -gon can be solved in O(n/sqrt(p)) time, if n > p2/4 .The maximum-perimeter triangle inscribed in a convex n -gon can be found in O(n/sqrt(p)) time, if n > p2 .The solutions to the two latter problems are based on the reduction of these problems to searching problems in totally monotone matrices
|
|
