Determinante de uma matriz generalizada de Vandermonde

10

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 n×n com algum número inteiro?

O determinante de Moore pode ser reduzido de O(n3) usando técnicas de FFT para O(nlogan) para alguns aR+{0} ?

A complexidade de Moore det modulo é um número inteiro e Vandermonde det o mesmo? A complexidade do determinante de Vandermonde é O(nlog2n) (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

T ....
fonte
O determinante de Moore pode mesmo ser calculado no tempo O (n ^ 3) (em uma RAM inteira)?
Jeffε
11
@ Jɛ ff E É por isso que eu mencionei modulo aleatório NN .
T ....
A propósito, e estou curioso, existem aplicativos conhecidos que se beneficiariam desse algoritmo "super-rápido"?
Juan Bermejo Vega
@J FFE, por acaso você sabe se computar uma exponenciação modular dobro sobre N está em BPP para trivial N ?. Porque isso é um problema para calcular os coeficientes da matriz. εNN
Juan Bermejo Vega

Respostas:

4

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)

Jeff Burdges
fonte
Oi Jeff: Qual referência você está referenciando para a fórmula O (n ^ 2). Penso que Vandermonde det pode ser calculado em O (nlogn), mas não consigo encontrar referência. Então Moore det também deveria estar em O (nlogn)?
T ....
Sim, eu deveria ter dito O (n) obviamente, realmente O (n log n) para n grande.
precisa saber é o seguinte
Oi Jeff: Você tem uma referência?
T ....
7
@JeffBurdges: se o tempo de execução é O (n log n) "para n grande", então, por definição, o tempo de execução é O (n log n), não O (n).
Jeffε
O(n)Θ(n2)
3

ZmmaqemodmO(log(mn)M(logm))

aqiaqi(modφ(m))(modm)
m

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.mO(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 .mmZm

Nota *: algoritmos mais rápidos para multiplicação de números inteiros permitem substituir por .log2mM(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×nMABL(M)=AMMBL(M)=MAMB

L(M)=k=1rgkhkT

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>0o(min{m,n})MdetMO(nlog2n)gkhk

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.

Juan Bermejo Vega
fonte
Eu posso fazer minha matriz viver em um campo de caractere . No entanto, o tamanho dos alfabetos para o meu aplicativo pretendido será grande. Então tem a forma para um suficientemente grande . 3m3kk
T ....
Isso é bom, desde que você pode calcular a função totient de :)3k
Juan Bermejo Vega
bem, isso não simplifica a complexidade, eu diria que o campo é muito, muito grande.
T ....
Simplifica os problemas mencionados com a dupla exponenciação. Como , você pode usar o teorema de Euler para exponenciar duas vezes : primeiro, calcule , então . Você pode fazer isso no tempo . Usando o algoritmo de multiplicação de escolas, , e você obteria um custo final "netto" de o que é eficiente. φ(3k)=3k3k1aqimodmb=qimodφ(3k)abmod3kO(log(n3k)M(klog3))M(n)=n2O(nωk2log23(logn+klog3))
Juan Bermejo Vega
Podemos substituir por ? Essa é a redução de custos em que estou curioso (pode ser possível na estrutura da matriz). Com , não ganho nada para o meu propósito. ω1+ϵω2
T ....