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)
Respostas:
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
fonte