Produto de matriz booleana esparsa rápida com possível pré-processamento

Quais são os algoritmos mais eficientes para multiplicar duas matrizes booleanas muito esparsas (por exemplo, N = 200 e existem apenas 100-200 elementos diferentes de zero)?

Na verdade, tenho a vantagem de que quando estou multiplicando A por B, os B são predefinidos e posso executar um pré-processamento arbitrariamente complexo neles. Sei também que os resultados dos produtos são sempre tão esparsos quanto as matrizes originais.

O algoritmo "bastante ingênuo" (varre A por linhas; para cada 1 bit da linha A, ou o resultado com a linha correspondente de B) resulta muito eficiente e requer apenas algumas milhares de instruções da CPU para calcular um único produto , portanto, não será fácil superá-lo e só poderá ser superado por um fator constante (porque há centenas de um bit no resultado). Mas não estou perdendo a esperança e pedindo ajuda à comunidade :)

ds.algorithms matrix-product sparse-matrix boolean-matrix implementation jkff
fonte

Duvido que possamos superar significativamente uma constante de 10 instruções da máquina por palavra de saída. É possível que alguma forma implícita da saída seja aceitável?

Warren Schudy 5/10/10

Sim, desde que possa ser multiplicado por Bs ainda mais.

Jkff #

Quais são as operações de adição e multiplicação (para bits) nas quais a multiplicação de matrizes é definida? Seu algoritmo ingênuo sugere que a resposta é "ou" e "e" respectivamente, mas isso é uma multiplicação de matriz bastante estranha, pois esses não definem um campo. Você quer dizer "xor" em vez de "ou"?

Warren Schudy 5/10/10

Não, quero dizer "ou" e "e". Não preciso das operações para definir um campo, isso é realmente um problema de acessibilidade de gráfico (estou computando a composição de várias funções de um para muitos).

JKFF

Respostas:

Eu relutava em responder a isso, porque o único resultado teórico que conheço nesse sentido tem meu nome no papel ...

$n \times n$ $A$ $A$ $n$

(Nota: esse algoritmo é realmente realmente útil para o caso em que uma matriz é densa e a outra é esparsa. Esse caso ocorre muito, por exemplo, ao calcular o fechamento transitivo de um gráfico esparso, a matriz de fechamento transitivo ficará densa. comparado à matriz de adjacência original.)

O papel é

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: Uma nova abordagem combinatória para problemas de gráficos esparsos. ICALP (1) 2008: 108-120

$\varepsilon > 0$ $O(n^{2+\varepsilon})$ $n \times n$ $A$

- Para qualquer vetor com apenas zero, pode ser calculado em , em que , são parâmetros livres que satisfazem . (Uma configuração legal é e , de modo que o tempo de execução seja aproximadamente para qualquer constante desejada . $v$ $t$ $A v$ $O(n(t/k + n/\ell)/\log n)$ $\ell$ $k$ ${\ell \choose k} \leq n^{\varepsilon}$ $\ell=\log^c n$ $k=\varepsilon(\log n)/\log \log n$ $nt/\log n + n^2/\log^c n$ $c$

- As atualizações de linha e coluna em podem ser calculadas em . $A$ $O(n^{1+\varepsilon})$

Usamos essa estrutura de dados para fornecer algoritmos teóricos mais rápidos para o APSP em gráficos esparsos não ponderados.

Ryan Williams
fonte

Acabei de notar que você também assume que a saída da multiplicação de matrizes também é escassa. Nesse caso, existem algoritmos ainda mais rápidos; faça uma pesquisa na web por "multiplicação de matriz sensível à saída".

Ryan Williams

Ryan Williams - Tenho uma pergunta rápida: você conhece ou já explorou algum método que generalize para poupar matrizes com valor de (em vez de simplesmente booleano)?

{- 1, 0, 1}

$\{-1, 0, 1\}$

Alexandre Cassagne

Eu acho que o que você chama de matriz "hiperespacial" (nnz <n). Alguns anos atrás, escrevi um artigo sobre como multiplicá-los. Essencialmente, é uma junção de produto externo com uma fusão inteligente de várias vias para eliminar a realização de triplos intermediários.

Buluc e Gilbert, IPDPS 2008: http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf

Aydin Buluc
fonte