<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-225

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Artur Czumaj, Parallel Algorithm for the Matrix Chain Product Problem (June 1, 1992).

Abstract

This paper considers the problem of finding an optimal order of the multiplication chain of matrices. All parallel algorithms known use the dynamic programming approach and run in a polylogarithmic time using, in the best case, n ⁶/log⁶n processors. Our algorithm uses a different approach and reduces the problem to computing some recurrence on a tree. We show that this recurrence can be optimally solved which enables us to improve the parallel bound by a few factors. Our algorithm runs in O (log³ n) time using n²/log³n processors on a CREW PRAM and O(log² n log log n ) time using n ²/(log²n log log n)processors on a CRCW PRAM. This algorithm solves also the problem of finding an optimal triangulation in a convex polygon. We show that for a monotone polygon this result can be even improved to get an O(log²n) time and n processor algorithm on a CREW PRAM.

<%@ include file="hardcopy.html" %> <%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>