Qual é a complexidade espacial do cálculo de valores próprios?

Estou procurando um documento de pesquisa ou um livro que cubra resultados sobre a complexidade espacial de operações comuns de álgebra linear, como classificação de matrizes, cálculo de valores próprios, etc. é mais fácil rastrear resultados de tempo. Agradeço qualquer referência sobre o assunto.

Obrigado.

linear-algebra space-complexity gil
fonte

Meu palpite é que a complexidade é sempre no máximo linear (por exemplo, para uma matriz ). Você está interessado em "espaço total" ou em "espaço de trabalho"?

O (n m)

$O(nm)$

n \times m

$n\times m$

Yuval Filmus

Eu deveria ter mencionado que estou interessado em espaço de trabalho.

Gil

Eu tenho certeza que é para uma matriz . A razão básica é que eu conheço dois métodos úteis para calculá-los e ambos são quadráticos no espaço. Primeiro, é computar o polinômio característico (quadrático) e encontrar as raízes. A segunda é usar alguns métodos de aproximação que todos precisam armazenar uma matriz modificada (mas não posso elaborar isso, já faz um tempo que eu estudava álgebra linear numérica).

O (n^{2})

$\mathcal O(n^2)$

n \times n

$n\times n$

yo '

Para expandir o argumento do @Yuval Filmus, a complexidade do espaço é bastante sensível ao modelo de computação específico. Em particular, como a saída é do tamanho linear, é possível executar truques usando a fita de saída como espaço de trabalho, a menos que o modelo especifique claramente uma fita de saída somente para gravação. Para evitar esses problemas, eu ficaria tentado a reformular os problemas de decisão (por exemplo, dados três matrizes de entrada, verifique se o terceiro é o produto dos dois primeiros). Você poderia especificar o modelo que tinha em mente? (Além disso, não conheço livros sobre a complexidade do espaço e também não encontrei nenhuma pesquisa útil.)

András Salamon

no que diz respeito ao @ AndrásSalamon, uma versão de decisão que seja útil para mim pode ser: o k'th autovalor é maior que q. para inteiro k e racional q. Obrigado.

Gil

Respostas:

As versões de decisão de muitos problemas comuns na álgebra linear sobre os números inteiros (ou racionais) estão na classe , consulte o artigo $\mathsf{DET}$

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Estrutura e Importância da Classe Logspace-MOD. Teoria dos Sistemas Matemáticos 25 (3): 223-237 (1992)

$\mathsf{DET}$ está contido em . $\mathsf{DSPACE}(\log^2)$

A computação dos valores próprios é um pouco mais delicada:

1) Em , pode-se calcular os coeficientes do polinômio característico. $\mathsf{DSPACE}(\log^2)$

2) Em seguida, você pode usar o algoritmo paralelo de Reif e Neff para calcular aproximações aos valores próprios. O algoritmo é executado em um CREW-PRAM em tempo logarítmico com muitos processadores polinomialmente, para que possa ser simulado com espaço polialogarítmico. (Não está explicitamente declarado no artigo, mas o PRAM deve ser uniforme no espaço de log.) O espaço usado é polilogarítmico no tamanho da matriz de entrada e na precisão . Precisão significa que você obtém aproximações até um erro aditivo de . $p$ $p$ $2^{-p}$

Esta é uma concatenação de funções computáveis no espaço poli-logarítmico. (As fitas de saída são apenas de gravação e de mão única.)

C. Andrew Neff, John H. Reif: um algoritmo eficiente para o problema de raízes complexas. J. Complexity 12 (2): 81-115 (1996)

Markus Bläser
fonte

$log^2$ $NC^2$

Lior Eldar
fonte