ランダム行列で遊んでみる (2)

前回のつづきです。次のグラフは 250 x 250 の実非対称行列の固有値の分布を複素平面上にプロットしたものです。

randommatrix3.png

このグラフが上下対称になることは、非常に簡単にわかります(前回参照)。
さらによーくみてみると、虚部がゼロな固有値がいくつか存在していることがわかります。
つまり、固有方程式が実根をもつ、ということですね。

もし本当に円盤の上にランダムに分布しているのならば、このようなことは決して起こらないでしょう(測度の意味で)。
一方で、この固有値たちはランダムな実係数の固有方程式
f(\lambda)=0の根となっていることを考えると、(ものすごくいい加減な言い方ですが)\(y=f(\lambda)\) のグラフはランダムに激しく振動しそうなので、 y=0 の直線と交わることは、0より大きな確率で起こりそうな気もします。

“ランダム行列で遊んでみる (2)”の続きを読む

ランダム行列で遊んでみる

ランダム行列というのは成分がランダムに与えられる行列のことです。
ランダム行列で普通問題になるのは、ランダムに生成された行列の固有値がどのように分布するか、
という問題のようです。

おもしろそうなので R を使って実験してみました。

1000次元の正方行列を考えて各要素は独立に標準正規分布に従うとします。
こうしてできる行列は実非対称な行列になります。

これを R で書くと

A=matrix(rnorm(1000000),nc=1000)
Eigen=eigen(A)
plot(Eigen$value,xlab="Re",ylab="Im")
title("Eigen value of real\nnonsymmetric 1000x1000 matrix")

となります(簡単!)。

以下が結果です。
不思議なことに円状に固有値が分布します。また、実軸に対して上下に対称に分布していることがわかります(これは固有方程式が実係数になるので、複素数解は必ず共役を解に持つ、ということから明らかですね)。

randommatrix.png

“ランダム行列で遊んでみる”の続きを読む

[C++] 列挙体 (enum) から名前(文字列)を取得するマクロ (2)

前回、列挙体 (enum) から名前(文字列)を取得するマクロについて書きました。前回のバージョンは

enum color {RED=1, BLUE=2, GREEN=4};

のような、値の変更に対応していませんでした。というわけで書き換え。

“[C++] 列挙体 (enum) から名前(文字列)を取得するマクロ (2)”の続きを読む

[C++] 列挙体 (enum) から名前(文字列)を取得するマクロ

C/C++ には列挙体があります。列挙体のタグは内部的には整数型として扱われますが、時々、タグの名前を文字列として取得できると便利だな、と思うことがあります。

マクロを使うと割と簡単に実現できます。下のソースコードの DECLARE_ENUM がそのマクロです。可変引数マクロを使っています。その下の main 関数の中では color という列挙体と colorName という文字列配列をDECLARE_ENUM マクロを使って同時に宣言しています。

この手のことはもちろん、文字列配列をまじめに定義すればよいのでどのくらい意味があるかはわかりませんが…
まあ、二度同じことを書かなくてよいのでタイピングは減るということがメリットでしょうか。

#include <iostream>
#include <string>
#include <vector>
#include <boost/foreach.hpp>
#include <boost/algorithm/string.hpp>

using namespace std;

#define DECLARE_ENUM(enumname, enumstr, ...)   \
enum enumname {__VA_ARGS__};                   \
boost::algorithm::split(enumstr, #__VA_ARGS__, boost::is_any_of(",")); \
do { BOOST_FOREACH(std::string &s, enumstr){ boost::trim(s); } } while(0)

int main()
{
  /* color is enum / colorName is vector<string> */
  vector<string> colorName;

  DECLARE_ENUM(color, colorName, RED, BLUE, GREEN);

  cout << RED   << ": " << colorName[RED] << endl;
  cout << BLUE  << ": " << colorName[BLUE] << endl;
  cout << GREEN << ": " << colorName[GREEN] << endl;
}

出力結果

0: RED
1: BLUE
2: GREEN

上の方法の欠点は定義をグローバルな場所に書くことができないことです。列挙体はグローバル変数として定義されることも多いのでこれは問題かもしれません。しかし、すこし書き換えればこの問題は回避できます。

“[C++] 列挙体 (enum) から名前(文字列)を取得するマクロ”の続きを読む

[Ruby] 10行で書ける Dijkstra 法

Dijkstra法はグラフ上の最短経路を求めるアルゴリズムです。このアルゴリズムの戻り値はある基点となるノードからその他のすべてのノードまでの距離の配列です。

解説はウェブ上にも豊富にあるので省略することにして、ここではどのくらい短いコード量で Dijkstra法を実装できるのか、という遊びをしてみます。仕様としては

  • 隣接リストではなく隣接行列を受け取る
  • ある二点間に辺が存在しない ⇔ 隣接行列の要素が負の値
  • ある辺の距離は隣接行列の正の要素で表現
  • 出力は指定した頂点からすべての頂点までの距離
  • 外部ライブラリを使用しない

くらいのものを考えましょう。

こんな感じになりました。

“[Ruby] 10行で書ける Dijkstra 法”の続きを読む

lp_solve で set_presolve したときの目的関数のリセット

以前、lp_solve で set_presolve したときの解の取得というエントリーを書きました。set_presolve は LP を解くための前処理の設定です。これが設定されると solve 関数の実行の際にいくつかの変数が配列から消去されてしまうため、インデックスの対応関係が崩れてしまいます。
前回のエントリーでは solve をした後に、インデックスの対応関係の崩れた lprec オブジェクトからどのように解を取り出せばよいのかについてでした。

今回のエントリーは「lprec オブジェクトのリサイクル」についてです。どういう状況を想定しているかというと、一度 solve が実行された lprec オブジェクトに対して

  • 制約条件はそのままで
  • 目的関数のみを変更する

という、一見すこしマニアックな設定です(実はこの状況は線形制約のシンプルな凸最適化アルゴリズムである、Frank-Wolfe 法を適用する場合に出現します)。

lp_solve ライブラリには set_obj_fn という関数がありますが、前述の理由でこの関数は一度 solve が実行された lprec オブジェクトに対しては使用することができません。

“lp_solve で set_presolve したときの目的関数のリセット”の続きを読む

lp_solve で set_presolve したときの解の取得

lp_solve は C/C++ から使える高性能の線形計画(LP)ソルバーだ。添え字の設定などに多少癖はあるが、中規模程度の問題ならほとんど問題なく利用できるし、なによりフリーなのがうれしい。

この lp_solve には、あらかじめ自明な解や一次従属な制約条件を取り除いてくれるset_presolve という前処理のための関数がある。前処理を行うかどうかは任意(デフォルトではしない)が、することを選択した場合は注意が必要だ。

解は get_variables という関数で取得できるが、前処理されて消去された変数はアルゴリズムの実行時には効率を優先するためにメモリから消されてしまうため、そのままではオリジナルの問題の変数の添え字に正しく対応する値を返してくれない。

“lp_solve で set_presolve したときの解の取得”の続きを読む