Resolvendo um sistema esparso e altamente mal condicionado

Pretendo resolver Ax = b onde A é uma matriz quadrada ou retangular complexa, esparsa, assimétrica e altamente mal condicionada (número de condição ~ 1E + 20). Consegui resolver o sistema com o ZGELSS no LAPACK com precisão. Mas, à medida que os graus de liberdade no meu sistema aumentam, leva muito tempo para resolver o sistema em um PC com ZGELSS, pois a dispersão não é explorada. Recentemente, tentei o SuperLU (usando o armazenamento da Harwell-Boeing) para o mesmo sistema, mas os resultados foram imprecisos para o número da condição> 1E + 12 (não tenho certeza se esse é um problema numérico com a rotação).

Estou mais inclinado a usar solucionadores já desenvolvidos. Existe um solucionador robusto que possa resolver o sistema que mencionei rapidamente (ou seja, explorar a escarsidade) e de forma confiável (em vista dos números de condição)?

linear-solver sparse-matrix lapack condition-number user1234
fonte

Você pode pré-condicionar? Nesse caso, os métodos do subespaço de Krylov podem ser eficazes. Mesmo se você insistir em métodos diretos, o pré-condicionamento ajudará a controlar erros numéricos.

amigos estão dizendo sobre geoff

Também fiz uma boa experiência com o pré-condicionamento da maneira descrita aqui: en.wikipedia.org/wiki/… Você pode fazer o pré-condicionamento na aritmética exata. Minhas matrizes, no entanto, são todas densas, portanto não podemos apontar para métodos / rotinas mais específicas aqui.

Alexe

Por que o número da condição é tão grande? Talvez a formulação possa ser melhorada para tornar o sistema melhor condicionado? Em geral, você não pode esperar para ser capaz de avaliar a mais residual precisão do que

, o que torna Krylov de pouco valor uma vez que você correr para fora de bits. Se o número da condição for realmente

, você deverá usar a precisão quad ( com o GCC, suportado por alguns pacotes, incluindo o PETSc).

(machine precision) \cdot (condition number)

$(\text{machine precision})\cdot(\text{condition number})$

10^{20}

$10^{20}$ __float128

Jed Brown

De onde você está obtendo essa estimativa de número de condição? Se você pedir ao Matlab para estimar o número da condição de uma matriz com um espaço nulo, isso poderá gerar infinito ou, às vezes, fornecer apenas um número realmente grande (como o que você possui). Se o sistema que você está vendo possui um espaço nulo e você sabe o que é, você pode projetá-lo e o que resta pode ter um número de condição melhor. Então você pode usar PETSc ou Trilinos ou o que você tem.

Daniel Shapero

min ‖ A x - b ‖

$\min \| Ax-b \|$

p e r p (N (A))

$perp(N(A))$

Respostas:

Ao usar o ZGELSS para resolver esse problema, você está usando a decomposição de valor singular truncado para regularizar esse problema extremamente mal condicionado. é importante entender que essa rotina da biblioteca não está tentando encontrar uma solução de mínimos quadrados para , mas está tentando equilibrar a localização de uma solução que minimizecontra minimizar. $Ax=b$ $\| x \|$ $\| Ax-b \|$

Observe que o parâmetro RCOND passado para o ZGELSS pode ser usado para especificar quais valores singulares devem ser incluídos e excluídos do cálculo da solução. Qualquer valor singular menor que RCOND * S (1) (S (1) é o maior valor singular) será ignorado. Você não nos contou como definiu o parâmetro RCOND no ZGELSS, e não falamos nada sobre o nível de ruído dos coeficientes na matriz ou no lado direito , por isso é difícil dizer se você usou uma quantidade adequada de regularização. $A$ $b$

Você parece estar satisfeito com as soluções regularizadas que está obtendo com o ZGELSS, portanto parece que a regularização efetuada pelo método SVD truncado (que encontra uma solução mínima entre as soluções de mínimos quadrados que minimizam no espaço de soluções abrangidas pelos vetores singulares associados aos valores singulares maiores que RCOND * S (1)) é satisfatório para você. $\| x \|$ $\| Ax-b \|$

Sua pergunta pode ser reformulada como "Como posso obter eficientemente soluções de mínimos quadrados regularizados para esse problema de mínimos quadrados lineares grandes, esparsos e muito mal condicionados?"

Minha recomendação seria usar um método iterativo (como CGLS ou LSQR) para minimizar o problema de mínimos quadrados explicitamente regularizado

$\min \| Ax-b \|^{2} + \alpha^{2} \| x \|^{2}$

onde o parâmetro de regularização é ajustado para que o problema de mínimos quadrados com amortecimento seja bem condicionado e para que você fique satisfeito com as soluções regularizadas resultantes. $\alpha$

Brian Borchers
fonte

Peço desculpas por não mencionar isso desde o início. O problema que está sendo resolvido é a equação de Helmholtz da acústica usando o MEF. O sistema está mal condicionado devido à base de onda plana usada para aproximar a solução.

usar o seguinte comando

A

$A$

b

$b$

As matrizes A e b são formadas usando a formulação fraca de Helmholtz PDE, consulte: asadl.org/jasa/resource/1/jasman/v119/i3/…

user1234

Jed Brown já apontou isso nos comentários da pergunta, mas realmente não há muito o que você possa fazer com precisão dupla usual se o número de sua condição for grande: na maioria dos casos, você provavelmente não terá um único dígito de precisão em sua solução e, pior, você nem sabe dizer porque não pode avaliar com precisão o resíduo correspondente ao seu vetor de solução. Em outras palavras: não é uma questão de qual solucionador linear você deve escolher - nenhum solucionador linear pode fazer algo útil para essas matrizes.

$1,x,x^2,x^3,...$

Wolfgang Bangerth
fonte

Ao discretizar um problema incorreto para um PDE, por exemplo, equação de calor inversa, definitivamente terminaremos com uma equação de matriz mal condicionada. Este não é o caso que podemos resolver reformulando a equação ou escolhendo um solucionador de matriz eficiente ou melhorando a precisão no número de ponto flutuante. Neste caso [isto é, problemas inversos acústicos], é necessário um método de regularização.

tqviet

A maneira mais simples / rápida de resolver problemas mal condicionados é aumentar a precisão dos cálculos (por força bruta). Outra maneira (ainda nem sempre possível) é reformular seu problema.

Pode ser necessário usar a precisão quádrupla (34 dígitos decimais). Mesmo que 20 dígitos sejam perdidos em um percurso (devido ao número da condição), você ainda terá 14 dígitos corretos.

Se isso for de seu interesse, agora os resolvedores esparsos de precisão quádrupla também estão disponíveis no MATLAB.

(Eu sou o autor da caixa de ferramentas mencionada).

Pavel Holoborodko
fonte