Finding All Successive Minimal Maximum Subsequences in Parallel

Start: 11/14/2016 - 4:15pm
End  : 11/14/2016 - 5:15pm

Applied Math Seminar

Ho-Kwak Dai (CMC; Oklahoma State University)


Efficient algorithms for finding multiple contiguous subsequences of a
real-valued sequence having large cumulative sums, in addition to its
combinatorial appeal, have widely varying applications such as in textual
information retrieval and bioinformatics. A maximum 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. We present an overlapping
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 a probabilistic length upper
bound for the common intersection of overlapping subsequences, which is
incorporated in the algorithm to facilitate the concurrent computation of
all minimal maximum subsequences in hosting processors.

*On sabbatical leave from Computer Science Department, Oklahoma State
University, Stillwater, Oklahoma 74078. Sincere thanks to Claremont McKenna
College for its hospitality.

Emmy Noether Room Millikan 1021 Pomona College