1
$\begingroup$

How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square)

First computing the matrix product and then extracting the diagonal can be suboptimal. Consider diagonal of outer product of two vectors uv'. We could get the diagonal by multiplying two vectors pointwise.

$$\text{diag}(uv')=u\odot v$$

enter image description here

More generally, we can compute diagonal of a square matrix product by viewing it as sum of outer products of rows/columns and applying the trick above $$AB=\sum_i u_i v_i' = \sum_i u_i \odot v_i$$

enter image description here

$\endgroup$

1 Answer 1

1
$\begingroup$

Use the standard dynamic programming algorithm to find the optimal cost of multiplying every subsequence of your matrices $A_1,\ldots,A_m$, which are of dimensions $d_1 \times d_2, d_2 \times d_3, \ldots, d_m \times d_{m+1}$. Assuming that the product matrix is $n \times n$ and that the optimal cost is $c(A_i \cdots A_j)$, the optimal cost for computing the diagonal of the product is $$ \min_{1 \leq i \leq n-1} c(A_1 \cdots A_i) + c(A_{i+1} \cdots A_m) + nd_{i+1}. $$ (The original problem has $n^2 d_{i+1}$ instead.)

You can compute the actual schedule in the usual way, by tracing the minimizer at each step of the dynamic programming.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.