Produto de cadeia de matriz booleana esparsa rápida

13

Então, eu tenho cerca de 100-200 matrizes booleanas quadradas muito esparsas com comprimento lateral ~ várias dezenas, e preciso calcular o produto delas. Sei que se os multiplicar em série, o produto geralmente permanecerá tão escasso a cada etapa.

Existem algoritmos de produtos em cadeia de matrizes que funcionam particularmente rápido nesse caso?

Em um nível mais alto, o problema é calcular a composição de uma série de mapeamentos um para muitos em um gráfico razoavelmente pequeno (funções de transição de uma NFA), onde a maioria dos elementos é mapeada para não mais que 0-3.

(observe que este não é o problema usual do "produto em cadeia da matriz", porque todas as matrizes são do mesmo tamanho e não preciso escolher o parênteses ideal)

jkff
fonte
5
na verdade, a ordem em que você os multiplica pode afetar a escassez dos resultados intermediários; portanto, ainda pode ser um problema importante em qualquer algoritmo rápido.
Joshua Grochow 14/09/10
a partir de sua outra pergunta que você parece estar usando 0/1 semianel E / OU operações, não adição / multiplicação (como o problema parece estado), por favor, deixar isso claro na questão
vzn

Respostas:

10

Isso foi muito longo para ser um comentário - eu me pergunto se essas matrizes têm estrutura que as faz se comportar de maneira diferente das matrizes aleatórias. Os produtos de matrizes esparsas aleatórias vão para zero ou tornam-se esparsos rapidamente.

Aqui está um experimento simples: faça 200 matrizes aleatórias binárias de 50x50 e plote o número de não-zeros como uma função do número de matrizes multiplicadas. Os gráficos abaixo mostram o desvio padrão em 2000 corridas. O primeiro gráfico é de 2% de dispersão, o segundo gráfico é de 3%


(fonte: yaroslavvb.com ) (fonte: yaroslavvb.com )

isso levou 3 minutos no meu laptop usando multiplicação de matriz padrão

Yaroslav Bulatov
fonte