Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal parallel evaluation of matrix product expressions (1992).
| Content Provider | CiteSeerX |
|---|---|
| Author | April, Amr Fahmy Fahmy, Amr F. |
| Abstract | We consider the problem of parallel evaluation of the expression M = M 1 \Theta M 2 \Theta M 3 : : : \Theta M n We demonstrate, using an example, that the optimal order for sequential evaluation is not necessarily optimal for parallel evaluation. There are two different levels of parallelism that we shall consider. The first is that of evaluating different products in parallel and the second is that of evaluating a single product using several processors. Given a matrix multiplication algorithm, sequential or parallel, we derive a Dynamic Programming algorithm that computes the minimum number of operations required for parallel evaluation of the expression. An algorithm that orders the evaluation process to achieve the minimum cost is also given. keywords: Design of Algorithms, Dynamic Programming, Matrix Multiplication Order, Parallel Algorithms Introduction Consider the problem of evaluating the expression M = M 1 \Theta M 2 \Theta M 3 : : : \Theta M n (1) where each M i is a... |
| File Format | |
| Publisher Date | 1992-01-01 |
| Access Restriction | Open |
| Subject Keyword | Optimal Parallel Evaluation Parallel Evaluation Matrix Product Expression Dynamic Programming Algorithm Dynamic Programming Sequential Evaluation Different Level Matrix Multiplication Order Several Processor Single Product Evaluation Process Minimum Cost Parallel Algorithm Introduction Consider Matrix Multiplication Algorithm Minimum Number Optimal Order Different Product |
| Content Type | Text |
