A matriz de Moore é semelhante à matriz de Vandermonde, mas possui uma definição ligeiramente modificada. http://en.wikipedia.org/wiki/Moore_matrix
Qual é a complexidade de calcular o determinante de um dado módulo n da matriz de Moore com algum número inteiro?
O determinante de Moore pode ser reduzido de usando técnicas de FFT para para alguns ?
A complexidade de Moore det modulo é um número inteiro e Vandermonde det o mesmo? A complexidade do determinante de Vandermonde é (Página 644 do Manual de Ciência da Computação Teórica: Algoritmos e Complexidade Por Jan Leeuwen)
Postagem semelhante à atual: módulo determinante m
Respostas:
Em geral, existe um algoritmo de tempo teórico para encontrar a decomposição da LU de uma matriz arbitrária usando o algoritmo Coppersmith – Winograd , que obviamente produz o determinante (adicionando tempo O ( n ) ). Existe um problema, no entanto, que o algoritmo Coppersmith – Winograd não é considerado utilizável na prática. Afaik, as pessoas usam principalmente o algoritmo Strassen de tempo O ( n 2.807 ) . O lu_factorize do Boost UBLAS não usa isso?O(n2.376) O(n) O(n2.807)
No seu caso, a matriz de Moore deve admitir otimizações consideráveis, porque basicamente qualquer procedimento de eliminação gaussiano como a decomposição da LU pode ser feito abstratamente. De fato, você encontrará uma boa fórmula para calcular o determinante de Moore referenciado pela wikipedia , o que presumivelmente se prova simplesmente calculando a decomposição da LU em geral.O(n)
fonte
Se for primo ou puder ser fatorado com eficiência, a pior complexidade é dominada pelo número de etapas necessárias para a multiplicação de matrizes . Por exemplo, a abordagem de forma normal de Smith que mencionei no post do parceiro calcularia o determinante no tempo se você usar "slow" algoritmos de multiplicação . pode ser escolhido como 2.373.m O(nω) O(nωlog2mlog(mn)) ∗ ω
Você tem uma desaceleração em Moore vs Vandermonde, pois é necessário exponenciar duas vezes os coeficientes da matriz. Quando você pode fatorar essa desaceleração é polilogarítmica em . Caso contrário, o algoritmo apresentado fornece uma redução de Cook para Exponenciação Modular Dupla em .m m Zm
Nota *: algoritmos mais rápidos para multiplicação de números inteiros permitem substituir por .log2m M(logmloglogm)
Atualização : sobre a possibilidade de obter .O(nlogan)
Não tenho uma resposta definitiva para isso, mas encontrei algumas informações que podem restringir sua pesquisa.
Algoritmos para matrizes estruturadas que calculam quantidades como determinantes no tempo são chamados "super-rápidos" na literatura. Todos os algoritmos "super-rápidos" conhecidos para matrizes estruturadas (Vandermonde, Toeplitz, Hankel) parecem confiar em uma propriedade comum dessas matrizes conhecida como "classificação de deslocamento" baixa. Consulte a discussão no primeiro capítulo deste livro (páginas de acesso aberto) ou neste artigo [ACM] , [PDF] .O(nlogan)
Pelo que li, dado um Moore matriz , se você fosse capaz de encontrar matrizes , tal que a nova matriz (ou, alternativamente, ) tem a seguinte estruturam×n M A B L(M)=AM−MB L(M)=M−AMB
e a classificação é pequena (constante ou delimitada por ), então você pode aplicar técnicas existentes (consulte o capítulo 5 do livro, abra acessar páginas) para triangularizar e, portanto, calcular , usando . Acima, , denotam vetores. Se você não encontrar o livro acima para ler a coisa toda, este artigo também possui muitas informações sobre esses métodos.r>0 o(min{m,n}) M detM O(nlog2n) gk hk
Infelizmente, não consegui encontrar uma estrutura de baixo deslocamento para a matriz de Moore (Vandermonde). A principal complicação aqui parece surgir da natureza "não linear" da dupla exponencial. Se ajudar, os casos de Vandermonde, Cauchy, Toeplitz e Hankel são elaborados no livro.
fonte