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

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences