Dissecação aninhada em grade regular

Ao resolver sistemas lineares esparsos usando métodos de fatoração direta, a estratégia de ordenação usada afeta significativamente o fator de preenchimento de elementos diferentes de zero nos fatores. Uma dessas estratégias de ordenação é a dissecação aninhada. Eu estou querendo saber se é possível obter a dissecção aninhada ordenando antecipadamente dados apenas os parâmetros da grade (assuma uma grade de diferença finita quadrada M x N com diferenças de primeira ordem).

Editar Acabei de descobrir que existe um código que faz isso: http://www.cise.ufl.edu/research/sparse/meshnd/

linear-algebra Victor Liu
fonte

Respostas:

Sim. Eu escrevi recentemente um código para fazer exatamente isso.

Suponha que você tenha uma grade e que seja aceitável ter nós de folha com 100 vértices. Pode-se então definir uma função recursiva onde os argumentos são: $n_x \times n_y$

as dimensões e compensações de um subdomínio retangular
um ponteiro em uma matriz que armazenará a reordenação

$\mathrm{natural}(x,y)=x+y n_x$ $n_x \times n_y$

Jack Poulson
fonte

Acho que minha pergunta é mais: a dissecação aninhada é realmente apenas recursivamente cortando o espaço pela metade? Além disso, a ordem é colocar os índices de limite à frente de cada metade direita e esquerda? Eu nunca encontrei uma explicação simples do que está acontecendo.

Victor Liu

Sim, a dissecção aninhada é muito direta, mas você armazena os índices de limite após as metades esquerda e direita. O objetivo é garantir que os dois subdomínios não estejam conectados diretamente; portanto, para diferenças finitas, é importante considerar o tamanho do seu estêncil ao decidir a espessura do separador. Eu recomendo que você leia a visão geral de Liu do método multifrontal e faça a conexão em que cada separador é tratado como um supernó.

precisa

Ah sim, eu percebi isso logo depois que comentei e depois fiz a edição. Obrigado pela referência.

Victor Liu