Using Fewer Processors to Reduce Time Complexities of Semigroup Computations

[[abstract]]For parallel algorithms, their execution time consists of two parts: the computation time and the communication time. The execution time reaches a minimum when the other two are balanced. This paper proposes a strategy to reduce the execution time when it is dominated by the communication time. The strategy is to use fewer processors to decrease the communication time and therefore reduce the execution time. The authors have successfully reduced time complexities of semigroup computations. To be more precise, any parallel algorithm performing semigroup computations of N data items can be improved if it uses N processors (each holds one data item) and has time complexity O(N super(q)log super(r)N), q greater than or equal to 0 and r greater than or equal to 0 (both are not zero)[[fileno]]2030209030028[[department]]資訊工程學