Fast and efficient parallel coarsest refinement
The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X;Y of the set U such that X = fX1;X2; : : : ;Xxg and Y = fY1;Y2; : : : ;Yyg, and determine a new partition...
Saved in:
Main Authors: | , |
---|---|
Format: | Journal |
Published: |
2018
|
Subjects: | |
Online Access: | https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014593240&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/57144 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Chiang Mai University |
id |
th-cmuir.6653943832-57144 |
---|---|
record_format |
dspace |
spelling |
th-cmuir.6653943832-571442018-09-05T03:45:17Z Fast and efficient parallel coarsest refinement Nopadon Juneam Sanpawat Kantabutra Computer Science Mathematics The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X;Y of the set U such that X = fX1;X2; : : : ;Xxg and Y = fY1;Y2; : : : ;Yyg, and determine a new partition Z = fZ1;Z2; : : : ;Zzg such that each Zc 2 Z is a common non-empty subset of some Xa 2 X and some Yb 2 Y and jZj is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t(n) + log n) parallel time using maxf n log n; p(n)g processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW PRAM. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(log n log( n log n)) parallel time using n log n processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm. 2018-09-05T03:35:28Z 2018-09-05T03:35:28Z 2017-01-01 Journal 01692968 2-s2.0-85014593240 10.3233/FI-2017-1465 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014593240&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/57144 |
institution |
Chiang Mai University |
building |
Chiang Mai University Library |
country |
Thailand |
collection |
CMU Intellectual Repository |
topic |
Computer Science Mathematics |
spellingShingle |
Computer Science Mathematics Nopadon Juneam Sanpawat Kantabutra Fast and efficient parallel coarsest refinement |
description |
The process of merging two arbitrary partitions of a given finite set U of n elements is known as coarsest refinement. In the COARSEST REFINEMENT PROBLEM we are given two arbitrary partitions X;Y of the set U such that X = fX1;X2; : : : ;Xxg and Y = fY1;Y2; : : : ;Yyg, and determine a new partition Z = fZ1;Z2; : : : ;Zzg such that each Zc 2 Z is a common non-empty subset of some Xa 2 X and some Yb 2 Y and jZj is as small as possible. This article describes a resource-efficient parallel algorithm to solve this problem. More specifically, we show that a coarsest refinement can be computed in O(t(n) + log n) parallel time using maxf n log n; p(n)g processors, where t(n) denotes the running time of a parallel stable sorting algorithm that uses p(n) processors on an EREW PRAM. This result depends on t(n) and p(n). We give a table that shows the best known time and processor complexities for a parallel stable sorting algorithm. If the parallel stable sorting algorithms by Ajtai et al., Cole, and Leighton are used, the coarsest refinement can be computed in O(log n) parallel time using n processors on an EREW PRAM. On the other hand, if the parallel stable sorting algorithm by Bahig et al. is used, the coarsest refinement can be computed in O(log n log( n log n)) parallel time using n log n processors on an EREW PRAM. In addition, we show that on, a RAM machine, our parallel algorithm runs as asymptotically efficient as the fastest known sequential algorithm. |
format |
Journal |
author |
Nopadon Juneam Sanpawat Kantabutra |
author_facet |
Nopadon Juneam Sanpawat Kantabutra |
author_sort |
Nopadon Juneam |
title |
Fast and efficient parallel coarsest refinement |
title_short |
Fast and efficient parallel coarsest refinement |
title_full |
Fast and efficient parallel coarsest refinement |
title_fullStr |
Fast and efficient parallel coarsest refinement |
title_full_unstemmed |
Fast and efficient parallel coarsest refinement |
title_sort |
fast and efficient parallel coarsest refinement |
publishDate |
2018 |
url |
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014593240&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/57144 |
_version_ |
1681424823873437696 |