Partial Matrix Multiplication Indexing

Preprocess an N×NN\times N matrix AA of real numbers and a collection S={S1,S2,,Sk}\mathcal S = \{S_1, S_2, \dots, S_k\} of sets of entries (SiN×NS_i\subseteq N\times N) so that given a sequence B1,,BkB_1, \dots, B_k of N×NN\times N matrices of real numbers, we enumerate the entries of A×BiA\times B_i that correspond to SiS_i.

Parameters

  • nn: dimension of square matrix
  • kk: number of sets in S\mathcal S
  • size(S)size(S): i=1kSi\sum_{i=1}^k |S_i|

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table