Advertisement
Published in:
2015 | OriginalPaper | Chapter
A Parallel Algorithm for Finding All Minimal Maximum Subsequences via Random Walk
Authors : H. K. Dai, Z. Wang
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A maximum(-sum) contiguous subsequence of a real-valued sequence is a contiguous subsequence with the maximum cumulative sum. A minimal maximum contiguous subsequence is a minimal contiguous subsequence among all maximum ones of the sequence. We have designed and implemented a domain-decomposed parallel algorithm on cluster systems with Message Passing Interface that finds all successive minimal maximum subsequences of a random sample sequence from a normal distribution with negative mean. Our study employs the theory of random walk to derive an approximate probabilistic length bound for minimal maximum subsequences in an appropriate probabilistic setting, which is incorporated in the algorithm to facilitate the concurrent computation of all minimal maximum subsequences in hosting processors. We also present a preliminary empirical study of the speedup and efficiency achieved by the parallel algorithm with synthetic random data.