Improved mesh algorithm for the maximum subarray problem

Sung E. Bae, PhD Student

Dept. of CSSE, University of Canterbury

Fri Feb 18 15:10:00 NZDT 2005 in Room 031, MSCS

Abstract

The maximum subarray problem is to find a rectangular portion in the given two dimensional array that maximizes the sum of the values of the array elements in the portion. This problem has wide applications in data mining and graphics. In data mining we can identify the most promising customer range from a large database of sales data. In graphics we can identify the brightest spot. While a subcubic time algorithm is best known solution, this processing speed is insufficient for real-time processing or large-scale data mining. Our mesh parallel algorithm offers good compromise between speed and cost. This mesh algorithm incorporates an n by n array processor, whose computing time is proportional to n, much faster than sequential processing.

In this seminar, we discuss how this mesh algorithm is further improved. We can reduce 25% of necessary inter-processor communication cost by bi-directional data transfer and eliminate data loading time before the execution.