spaghetti-source

// n-gram graph G = (V,E)
//   V: set of n-grams (i.e., n-tuple of words)
//   E: u->v iff v is a next n-gram of v in the document
//
// Usage: ./a.out < pg11.txt
// ( http://www.gutenberg.org/cache/epub/11/pg11.txt )
//
// the_march_hare 0.224377
// march_hare_said 0.04768
// march_hare_interrupted 0.02384

spaghetti-source

// n-grams graph G = (V,E)
//   V: set of n-grams (i.e., n-tuple of words for n = 1 .. N )
//   E: u->v iff v is a next n-gram of v in the document
//
// Usage: ./a.out < pg11.txt
// ( http://www.gutenberg.org/cache/epub/11/pg11.txt )
//
#include <iostream>
#include <vector>
#include <cstdio>

spaghetti-source

MNISTデータセットで遊ぼう

概要

MNISTデータセットは0～9の数字を手書きした画像のデータセットであり，以下からダウンロードできる：

http://yann.lecun.com/exdb/mnist/

spaghetti-source

%
% Modified (numerical stable) version of Walker and Zhou's Simpler GMRES.
%
% Homer F. Walker and Lu Zhou (1994): A simpler GMRES. 
%   Numerical Linear Algebra and Applications, Vol.1, No.6, 571-581.
% ( http://users.wpi.edu/~walker/Papers/gmres-simpler,NLAA_1,1994,571-581.pdf )
% 

n = 100;
A = diag( log( [2:n+1] ) ) + randn(n);

spaghetti-source

n = 400;
A = diag( log( [2:n+1] ) ) + randn(n) / n;
b = randn(n,1);
y = A \ b;
EPS = 1e-8;


% GCR
disp(' '); disp('GRR');
tic;

spaghetti-source

// 
// Newton-Krylov method
//
// The Newton method is:
//   Step 1. solve H(x) u = g(x), where H is a Hessian and g is a gradient.
//   Step 2. update x = x - u.
// This is a second order method, which requires a Hessian information.
// On the Newton-Krylov method, Step 1 is implemented as
//   (a) solve this equation by iterative (Krylov subspace) method.
//   (b) use numerical difference to LHS evaluation, i.e.,

spaghetti-source

%
% solve   min c'x s.t. Ax >= b, x in {0,1}^n
% 
% Lagrangian L(x,u) := cx + ub - uAx
%
% original problem:
%   min[x] max[u] L(x,u) 
% Lagrangian dual
%   max[u] min[x] L(x,u)
%

spaghetti-source

// 
// Zero-suppressed binary decision diagram with family algebra operations
//
// References: 
//   S. Minato (1993): 
//     Zero-suppressed BDDs for set manipulation in combinatorial problems.
//     Proceedings of the 30st annual Design Automation Conference, pp. 272-277.
//   S. Minato (1994):
//     Calculation of unate cube set algebra using zero-suppressed BDDs.
//     Proceedings of the 31st annual Design Automation Conference, pp. 420-424.

spaghetti-source

// Runtime error if compile with "g++ -O3 main.cc"
#include <iostream>
#include <Eigen/Eigen>

using namespace std;
using namespace Eigen;

void f() {
  MatrixXd U(2,2);
  U = U*U; // runtime error

spaghetti-source

#pragma once
#include <vector>

typedef unsigned short WORD;
typedef unsigned long DWORD;
typedef long           LONG;
typedef unsigned char  BYTE;
#pragma pack(push, 1)
struct BITMAPFILEHEADER {
  WORD  bfType;