TAUCS を使う

2021年2月2日

はじめに

マトリックスソルバー TAUCS を使う。

バージョン

  • TAUCS Version 2.2
  • Ubuntu 16.04 LTS
  • Windows 7、MSYS2/MinGW 64 bit
  • Windows 10、Visual Studio 2019 (16.8.4)

TAUCS のコンパイル (Ubuntu)

ここ からパッケージを入手する。いくつかあるが、"Version 2.2 of the code, no external libraries, tgz format" でよい。

そのまま展開するとファイルが散らかるので、ディレクトリを作成してから展開する。

$ mkdir taucs
$ mv taucs.tgz taucs
$ cd taucs
$ tar xvzf taucs.tgz

基本的な操作は、configure, make のみ。

$ ./configure
cc -o configurator/configurator configurator/taucs_config.c
configurator/taucs_config.c: In function ‘emit_configfile’:
configurator/taucs_config.c:244:5: warning: implicit declaration of function ‘mkdir’ [-Wimplicit-function-declaration]
     mkdir(configdir);
     ^

警告が出ているが、気にしなくてよさそう。

$ make

cilk のエラーが出るが無視してよい。

コンパイルした環境では、いつくかエラーが出たので、以下の処置をとった。

パッケージのインストール。

$ sudo apt-get install libatlas-base-dev
$ sudo apt-get install libmetis-dev

config/linux.mk を編集。FC を修正。

FC        = gfortran #g77

CFLAGS がたくさんあるので、それらの最後に以下を追加 (それより上のものを上書き)。

CFLAGS    = -O3 -Wall

LIBF77 を修正。

LIBF77 = -lgfortran #-lg2c

これでコンパイルはできるが、テストプログラムでリンクして実行してみると、METIS のエラーらしきものが出る。

$ ./a.out
taucs_linsolve: preparing to factor
taucs_linsolve: ordering (llt=1, lu=0, ordering=metis)
 Runtime parameters:
   Objective type: Unknown!
   Coarsening type: Unknown!
   Initial partitioning type: Unknown!
   Refinement type: METIS_RTYPE_FM
   Perform a 2-hop matching: Yes
   Number of balancing constraints: 1
   Number of refinement iterations: 0
   Random number seed: 0
   Number of separators: 1094145072
   Compress graph prior to ordering: No
   Detect & order connected components separately: Yes
   Prunning factor for high degree vertices: 0.000000
   Allowed maximum load imbalance: 33.765

METIS のバージョンが新しいとダメらしい (Ver. 5 だとダメ?)。

METIS のコンパイル

TAUCS Version 2.2 は 2003 年にリリースされているので、その近辺にリリースされたバージョンの METIS を用いる。ここでは METIS 4.0.3 を用いた。こちらからダウンロードする。

$ tar xvzf metis-4.0.3.tar.gz
$ cd metis-4.0.3
$ make

TAUCS の再コンパイル

config/linux.mk を修正。コンパイルした METIS を使うようにする。

#LIBMETIS  = -L external/lib/linux -lmetis
LIBMETIS  = -L../metis-4.0.3 -lmetis

コンパイル。

$ make clean
$ make

インストール

インストールスクリプトはなさそうなので、以下のようなものを作った。

install

#!/bin/sh
INSTALL_DIR=../build
INCLUDE=$INSTALL_DIR/include
LIB=$INSTALL_DIR/lib

mkdir -p $INCLUDE
cp build/linux/*.h $INCLUDE
cp src/taucs.h $INCLUDE
cp src/taucs_private.h $INCLUDE

mkdir -p $LIB
cp lib/linux/*.a $LIB
cp ../metis-4.0.3/libmetis.a $LIB

コンパイルした METIS の静的ライブラリもコピーしている。

TAUCS のコンパイル (MSYS2/MinGW 64 bit)

必要なパッケージを入れる。

$ pacman -S mingw64/mingw-w64-x86_64-lapack

ここで METIS をインストールすることもできるが、バージョンが新しいためか実行時にオーダリングに失敗する。Linux 同様に METIS 4.0.3 を用いる。

$ tar xvzf metis-4.0.3.tar.gz
$ cd metis-4.0.3

コンパイルオプションを追加。

Makefile.in

COPTIONS = -D__VC__

コンパイル。

$ make

TAUCS のコンパイルでもいくつか修正が必要。config/linux.mk をコピーして config/msys.mk を作る。以下のように修正。

FC        = gfortran #g77
CFLAGS    = -O3 -Wall -DOSTYPE_win32
#LIBBLAS   = -L external/lib/linux -lf77blas -lcblas -latlas
#LIBLAPACK = -L external/lib/linux -llapack
LIBBLAS   = -L/mingw64/lib -lcblas -lblas
LIBLAPACK = -L/mingw64/lib -llapack
#LIBMETIS  = -L external/lib/linux -lmetis
LIBMETIS  = -L../metis-4.0.3 -lmetis
LIBF77 = -lgfortran #-lg2c

ソースを一部修正する。src/taucs.h の以下の部分をコメントにする。

typedef unsigned long ssize_t;
typedef int mode_t;

コンパイル自体は Linux と同様。

TAUCS のコンパイル (Visual Studio 2019)

TAUCS のサイトから "Version 2.2 of the code, with external libraries, zip format" をダウンロードする。

TAUCS

32 bit 版だったら、x86 開発コマンドプロンプトで以下のようにすればよい。

>configure
>nmake

64 bit 版だと、x64 開発コマンドプロンプトで実行するが、別途外部ライブラリを自分で用意する必要がある。それはそれとして、一度実行しておく。

>configure
>nmake

external\lib\win32 に外部ライブラリが入っているが、これに相当するものを 64 bit ように用意する必要がある。x64 フォルダを作成。

BLAS/LAPACK

Netlib からバイナリを入手できる。

  • BLAS_nowrap.lib
  • clapack_nowrap.lib

TAUCS の external\lib\x64 フォルダに入れる。libf2c.lib もあるが、これではうまくいかなかった。

F2C

Netlib からソースを入手。

  • libf2c.zip

x64 開発コマンドプロンプトで、以下を実行。

>nmake -f makefile.vc

vcf2c.lib ができるので、libf2c.lib という名前で TAUCS の external\lib\x64 フォルダに入れる。

METIS

Linux 同様に Ver. 4.0.3 のソースを入手。

Visual Studio で自分でプロジェクトを作る。いくつか設定と修正が必要。

  • metis.h の中の strings.h のインクルードをコメントにする。

プロジェクトのプロパティについて、以下の設定を行う。

  • [全般]-[構成の種類] を "スタティックリンク (.lib)" にする。
  • [C/C++]-[全般]-[追加のインクルーディディレクトリ] に Lib フォルダのパスを追加する。
  • [C/C++]-[全般]-[SDL チェック] を "いいえ (/sdl)" にする。
  • [C/C++]-[プリプロセッサ]-[プリプロセッサの定義] に __VC__ を追加する。
  • [C/C++]-[コード生成]-[ランタイムライブラリ] を "マルチスレッド (/MT)" にする。

libmetis.lib という名前で TAUCS の external\lib\x64 フォルダに入れる。

TAUCS (再)

config\win32.mk の最後に以下を追加する。

LIBBLAS   = external\\lib\\x64\BLAS_nowrap.lib
LIBLAPACK = external\\lib\\x64\\clapack_nowrap.lib
LIBF77    = external\\lib\\x64\\libf2c.lib
LIBMETIS  = external\\lib\\x64\\libmetis.lib

再度コンパイル。

>nmake

テスト

テストプログラムをコンパイル、実行してみる。作業ディレクトリを test とし、テストプログラムを test.c とする。

Makefile は、雑だが次のようにする。

test/Makefile

all:
  gcc test.c -I../build/include -L../build/lib -ltaucs -lf77blas -lcblas -latlas -llapack -lmetis-edf -lf2c -lgfortran -lm

コンパイル、実行。

$ cd test
$ make
$ ./a.out
taucs_linsolve: preparing to factor
taucs_linsolve: ordering (llt=1, lu=0, ordering=metis)
taucs_linsolve: ordering time 0.00e+00 seconds (0.00e+00 seconds CPU time)
taucs_linsolve: starting LLT factorization
taucs_linsolve: pre-factorization permuting of A
taucs_linsolve: starting IC LLT factorization
taucs_linsolve: starting IC LLT MF factorization
    Elimination tree depth is 3
    Symbolic Analysis of LL^T: 8.00e+00 nonzeros, 2.20e+01 flops, 2.85e+02 bytes in L
    Relaxed  Analysis of LL^T: 1.00e+01 nonzeros, 3.40e+01 flops, 3.33e+02 bytes in L
    Symbolic Analysis            =      0.000 seconds (0.000 cpu)
    Supernodal Multifrontal LL^T =      0.000 seconds (0.000 cpu)
taucs_linsolve: preparing to solve
taucs_linsolve: pre-solve permuting of A
x =
      1.000e+00
      3.000e+00
      4.000e+00
      2.000e+00

問題なし。

テストプログラム

test.c

/*
 * TAUCS Test
 *
 * [ 2 -1  0  0] [ ]   [-1]
 * [-1  3 -1  0] [x] = [ 4]
 * [ 0 -1  3 -1] [ ]   [ 7]
 * [ 0  0 -1  2] [ ]   [ 0]
 */
#include <stdio.h>

#define TAUCS_CORE_DOUBLE
#include <taucs.h>


int main(void)
{
  taucs_ccs_matrix *a;
  taucs_double b[] = {-1., 4., 7., 0.};
  taucs_double x[4];
  char *options[] = {"taucs.factor.LLT=true", "taucs.factor.mf=true", NULL};
  //char *options[] = {"taucs.factor.LLT=true", "taucs.solve.cg=true", NULL};
  int i;

  taucs_logfile("stdout");

  a = taucs_ccs_create(4, 4, 7, TAUCS_DOUBLE|TAUCS_SYMMETRIC|TAUCS_LOWER);

  a->colptr[0] = 0;
  a->colptr[1] = 2;
  a->colptr[2] = 4;
  a->colptr[3] = 6;
  a->colptr[4] = 7;

  a->rowind[0] = 0;
  a->rowind[1] = 1;
  a->rowind[2] = 1;
  a->rowind[3] = 2;
  a->rowind[4] = 2;
  a->rowind[5] = 3;
  a->rowind[6] = 3;

  a->taucs_values[0] =  2.;
  a->taucs_values[1] = -1.;
  a->taucs_values[2] =  3.;
  a->taucs_values[3] = -1.;
  a->taucs_values[4] =  3.;
  a->taucs_values[5] = -1.;
  a->taucs_values[6] =  2.;

  //taucs_ccs_write_ijv(a, "amat.txt");

  if(taucs_linsolve(a, NULL, 1, x, b, options, NULL) != TAUCS_SUCCESS){
    printf("solution failed\n");
    return 0;
  }

  printf("x =\n");
  for(i = 0; i < 4; i++) printf("%15.3e\n", x[i]);

  taucs_ccs_free(a);

  return 0;
}

CCS

TAUCS は、マトリックスの圧縮格納形式を扱うことができる。対称行列を CCS (Compressed Column Storage) で配列に格納する場合には、次のようになる。

a =

  [ 2 -1  0  0]
  [-1  3 -1  0]
  [ 0 -1  3 -1]
  [ 0  0 -1  2]

※インデックスは 0 から開始

value = [2, -1, 3, -1, 3, -1, 2]  非 0 要素
column = [0, 2, 4, 6, 7]          対角要素のインデックス。最後の値は非0要素の数
row = [0, 1, 1, 2, 2, 3, 3]       非 0 要素の行のインデックス

要素 a(i, j) へのアクセスは、次のようになる。

k: row(k) = i and column(j) <= k < column(j+1)
a(i, j): value(k)

例) a(2, 1) の場合

column(1) = 2, column(2) = 4
2 <= k < 4 and row(k) = 2 -> k = 3
a(2, 1): value(3) = -1

例) a(3, 3) の場合

column(3) = 6, colume(4) = 7
6 <= k < 7 and row(k) = 3 -> k = 6
a(3, 3): value(6) = 2