Qual é a relação do BLAS, LAPACK e outras bibliotecas de álgebra linear?

26

Eu tenho procurado em bibliotecas de álgebra linear C ++ para um projeto que eu tenho trabalhado. Algo que ainda não entendi é a conexão do BLAS e LAPACK a outras bibliotecas de álgebra linear.

Examinando este artigo sobre bibliotecas de álgebra linear, achei interessante que:

  • algumas bibliotecas são independentes do BLAS e LAPACK
  • alguns requerem BLAS e LAPACK
  • alguns têm interfaces opcionais para BLAS e LAPACK
  • e, pelo que entendi, você pode usar BLAS e LAPACK para resolver problemas de álgebra linear diretamente

Eu posso imaginar que algumas bibliotecas são simplesmente interfaces C ++ para bibliotecas BLAS e LAPACK escritas em C e Fortran e outras implementaram suas próprias rotinas de substituição, mas

  1. Quais são as implicações das interfaces opcionais para BLAS e LAPACK? O que você está perdendo ao optar por sair e o que as bibliotecas estão fazendo?

  2. Alguma das bibliotecas fornece mais do que apenas uma interface? Por exemplo, UMFPACK é escrito em C e possui interfaces opcionais para BLAS e LAPACK. O que o UMFPACK (ou outras bibliotecas) faz com que o BLAS e o LAPACK não possam sozinhos?

Neal Kruis
fonte

Respostas:

15

Até onde eu sei, Lapack é a única implementação disponível publicamente de vários algoritmos (resolvedor denso não simétrico, resolvedor simétrico de tempo pseudo-quadrático e simétrico, rápido Jacobi SVD). A maioria das bibliotecas que não dependem do BLAS + Lapack tendem a suportar operações muito primitivas, como multiplicação de matrizes, fatoração de LU e decomposição de QR. O Lapack contém alguns dos algoritmos mais sofisticados para cálculos de matriz densa que não acredito que sejam implementados em nenhum outro lugar.

Então, para responder às suas perguntas (pelo menos parcialmente),

  1. Ao optar pelo BLAS / Lapack, normalmente você não está perdendo a funcionalidade (a menos que a interface opcional tenha sido projetada para que não haja implementação substituta, o que é raro). Se você deseja realizar operações muito sofisticadas, essas outras bibliotecas provavelmente não as implementam de maneira alguma. Como o BLAS pode ser altamente ajustado para sua arquitetura, você pode estar perdendo grandes acelerações (uma diferença de velocidade de ordem de magnitude não é inédita).

  2. Você mencionou UMFPACK, que é para fatoração de matriz esparsa. BLAS / Lapack está preocupado apenas com matrizes densas. Em algum nível, o UMFPACK precisa trabalhar em problemas densos de tamanho médio, o que pode ser feito usando implementações personalizadas ou chamando BLAS / Lapack. Aqui a diferença está apenas na velocidade.

Se a velocidade for motivo de grande preocupação, tente usar uma biblioteca que suporte ligações BLAS / Lapack opcionais e use-as no final quando quiser coisas mais rápidas.

Victor Liu
fonte
3
  1. Boas implementações das rotinas BLAS e LAPACK (principalmente as rotinas BLAS) podem ser muito mais rápidas que as implementações simples e ingênuas das mesmas funções. No entanto, implementações eficientes geralmente incluem otimizações muito específicas para o computador específico em que você está executando. Mesmo modelos diferentes de processadores do mesmo fabricante (por exemplo, processadores Intel x86-64) geralmente exigem código muito diferente para obter um bom desempenho. Ao fornecer bibliotecas BLAS / LAPACK otimizadas para um pacote de software, normalmente você pode acelerar o código comparado ao uso de rotinas não otimizadas. No entanto, como muitos usuários casuais podem não ter o conhecimento necessário para instalar rotinas otimizadas, é comum também fornecer uma opção para usar rotinas genéricas de álgebra linear não otimizadas.

  2. UMFPACK é uma biblioteca de rotinas para álgebra linear em matrizes esparsas (matrizes com uma alta proporção de 0 entradas.) Ele pode usar BLAS / LAPACK para lidar com matrizes densas (ou blocos densos dentro de matrizes) que encontrar.

Brian Borchers
fonte
1

Versão curta: são bibliotecas escritas principalmente no Fortran que são usadas para operações numéricas em muitos idiomas - até mesmo alguns programas em C devido à sua velocidade e otimizações; Eles também são algumas das únicas implementações de código aberto de muitos algoritmos :)

Você não precisa usar bibliotecas, a menos que tenham dependências; iirc a maioria deles é bastante independente e você sempre pode escrever suas próprias funções matemáticas, como as melhores vetorizadas para sua arquitetura

Eiyrioü von Kauyf
fonte
1
As rotinas BLAS e LAPACK mais otimizadas deixaram de ser escritas Fortran. As rotinas mais rápidas do BLAS e LAPACK geralmente não são as baixadas do netlib. Os fornecedores da maioria dos processadores vendem ou distribuem versões otimizadas do BLAS e LAPACK projetadas especificamente para seus chips.
Bill Barth
Desculpe, quero dizer os distribuídos na rede - os gerais; é claro que os específicos de chips não são tão portáteis: ou seja, alguns dos truques vetoriais da Intel não funcionam tão bem nos chips AMD, e é por isso que eles têm um aviso sobre a biblioteca. E tenho certeza de que esses são renomeados com outro nome, não?
Eiyrioü de Kauyf
@ BillBarth BLAS definitivamente, mas você tem certeza de que as rotinas LAPACK também são reescritas? Desde que o BLAS 3 tenha alto desempenho (ou multithread), tudo ficará bem.
Stali
1
Penso no BLAS e no LAPACK como os nomes das funções e da interface. Existem muitas implementações diferentes (ACML, ESSL, MKL, ATLAS, etc.).
Bill Barth
1
essas são apenas interfaces ... como o ATLAS, elas não são a biblioteca real.
Eiyrioü de Kauyf