algebra API

Luna-Flow/linear-algebra/algebra は、ベクトルや行列のオブジェクト全体が実装する構造 trait を定義します。形状、閉じた加法構造、Hadamard 乗算、転置、行列積です。各 trait は一つ下の trait より能力を一つだけ多く要求するので、汎用アルゴリズムは実際に使うものだけを正確に指定できます。このパッケージには型も関数もありません。リポジトリ自身の稠密型に対する実装は backends/default にあります。

ソース: src/algebra/linear_traits.mbt。階層の背後にある数学は algebra の設計 で、外部の型がどのレベルを選ぶべきかは 統合ガイド で説明しています。

インポート

///|
import {
  "Luna-Flow/linear-algebra/algebra",
}

trait 階層

Trait	スーパートレイト	追加されるもの
VectorShape	なし	length
AdditiveVector	VectorShape + Add + Neg + Sub	閉じた +、単項 -、二項 -
VecMulVector	AdditiveVector + Mul	要素ごとの（Hadamard）*
MatrixShape	なし	shape
TransposeMatrix	MatrixShape	同じ型への transpose
AdditiveMatrix	TransposeMatrix + Add + Neg + Sub	閉じた +、単項 -、二項 -
MatMulMatrix	AdditiveMatrix + Mul	行列積 *

すべての trait は pub(open) です。どのパッケージも自分が所有する型に対して実装できます。演算子 trait Add、Neg、Sub、Mul は MoonBit 組み込みの trait なので、あるレベルに加わった型は通常の演算子をそのまま使い続けられます。

形状 trait

VectorShape

VectorShape は長さを観測できるオブジェクトを表します。

pub(open) trait VectorShape {
  fn length(Self) -> Int
}

演算も要素アクセスも主張しません。長さ $n$ のベクトルは、実装が $\{0, \dots, n-1\}$ と対応付けるある集合の元であり、trait が公開するのは $n$ だけです。

VectorShape::length

VectorShape::length はベクトルの成分数を返します。

fn VectorShape::length(Self) -> Int

このリポジトリのすべての実装で結果は非負です。汎用コードでは trait で修飾した形式 @algebra.VectorShape::length(v) で呼び出してください。具体型が独自の length メソッドを公開している場合もあります。

MatrixShape

MatrixShape は行数と列数を観測できるオブジェクトを表します。

pub(open) trait MatrixShape {
  fn shape(Self) -> (Int, Int)
}

MatrixShape::shape

MatrixShape::shape は (rows, cols) を返します。

fn MatrixShape::shape(Self) -> (Int, Int)

どちらの成分も非負です。退化した形状 $0 \times n$ と $n \times 0$ も有効な行列であり、そのとおりに報告しなければなりません。

次の例は二つの小さな型に両方の形状 trait を実装し、汎用形式で読み戻します。

///|
struct AlgApiToyMatrix {
  rows : Int
  cols : Int
}

///|
struct AlgApiToyVector {
  size : Int
}

///|
impl @algebra.MatrixShape for AlgApiToyMatrix with fn shape(self) {
  (self.rows, self.cols)
}

///|
impl @algebra.VectorShape for AlgApiToyVector with fn length(self) {
  self.size
}

///|
test "shape traits report dimensions" {
  let matrix : AlgApiToyMatrix = { rows: 2, cols: 3, }
  let vector : AlgApiToyVector = { size: 4, }
  debug_inspect(@algebra.MatrixShape::shape(matrix), content="(2, 3)")
  inspect(@algebra.VectorShape::length(vector), content="4")
}

ベクトル trait

AdditiveVector

AdditiveVector は、値が + について可換群をなすベクトル型を表します。

pub(open) trait AdditiveVector : VectorShape + Add + Neg + Sub {
}

この trait 自体にはメソッドがありません。実装することは、同じ長さの値について次が成り立つことの約束です。

$$\begin{aligned} (u + v) + w &= u + (v + w), & u + v &= v + u, \\ (u + (-u)) + v &= v, & u - v &= u + (-v), \end{aligned}$$

また、結果はオペランドの長さを保ちます。この trait は大域的な零、スカラー作用、内積、ノルムを要求しません。理由は 設計ページ を参照してください。長さが等しいことは実行時の事前条件であり、このリポジトリの実装は長さが一致しないと中断します。

VecMulVector

VecMulVector は要素ごとの（Hadamard）積 $(u \odot v)_i = u_i v_i$ を * として追加します。

pub(open) trait VecMulVector : AdditiveVector + Mul {
}

* は Hadamard 積を意味しなければならず、内積や外積であってはなりません。これにより、環 $R$ 上の固定長 $n$ のベクトルは直積環 $R^n$ をなし、* は結合的で + に対して分配的になります。

この例はレベルごとにヘルパーを一つ書き、成分が一つのおもちゃの型で実行します。

///|
struct AlgApiMulVec {
  value : Int
}

///|
impl @algebra.VectorShape for AlgApiMulVec with fn length(_) {
  1
}

///|
impl Add for AlgApiMulVec with fn add(left, right) {
  { value: left.value + right.value, }
}

///|
impl Neg for AlgApiMulVec with fn neg(value) {
  { value: -value.value, }
}

///|
impl Sub for AlgApiMulVec with fn sub(left, right) {
  left + -right
}

///|
impl Mul for AlgApiMulVec with fn mul(left, right) {
  { value: left.value * right.value, }
}

///|
impl @algebra.AdditiveVector for AlgApiMulVec

///|
impl @algebra.VecMulVector for AlgApiMulVec

///|
fn[V : @algebra.AdditiveVector] alg_api_difference(left : V, right : V) -> V {
  left - right
}

///|
fn[V : @algebra.VecMulVector] alg_api_hadamard(left : V, right : V) -> V {
  left * right
}

///|
test "vector traits expose closed operators" {
  let left : AlgApiMulVec = { value: 7, }
  let right : AlgApiMulVec = { value: 3, }
  inspect(alg_api_difference(left, right).value, content="4")
  inspect(alg_api_hadamard(left, right).value, content="21")
}

行列 trait

TransposeMatrix

TransposeMatrix は転置について閉じた行列型を表します。

pub(open) trait TransposeMatrix : MatrixShape {
  fn transpose(Self) -> Self
}

TransposeMatrix::transpose

TransposeMatrix::transpose は転置 $A^{\mathsf T}$（$(A^{\mathsf T})_{ij} = A_{ji}$）を同じ型の値として返します。

fn TransposeMatrix::transpose(Self) -> Self

実装は次を満たさなければなりません。

$$\operatorname{shape}(A^{\mathsf T}) = (n, m) \text{ when } \operatorname{shape}(A) = (m, n), \qquad (A^{\mathsf T})^{\mathsf T} = A .$$

転置は全域的で、どの形状でも失敗しません。この trait は稠密な格納、要素アクセス、変更を要求せず、結果が引数と格納領域を共有するかどうかも規定しません。

AdditiveMatrix

AdditiveMatrix は転置可能な行列型に、閉じた要素ごとの +、単項 -、二項 - を追加します。

pub(open) trait AdditiveMatrix : TransposeMatrix + Add + Neg + Sub {
}

法則は同じ形状の行列に対する AdditiveVector の法則と、$(A + B)^{\mathsf T} = A^{\mathsf T} + B^{\mathsf T}$ です。形状が等しいことは実行時の事前条件です。

MatMulMatrix

MatMulMatrix は行列積を * として追加します。

pub(open) trait MatMulMatrix : AdditiveMatrix + Mul {
}

* は積 $(AB)_{ik} = \sum_j A_{ij} B_{jk}$ でなければならず、決して Hadamard 積ではありません。左オペランドの列数が右オペランドの行数と等しいときにだけ定義されるので、実行時に形状が決まる行列では部分演算です。この trait は定義域の外で何が起こるかを標準化しないため、各実装がそれを文書化しなければなりません。backends/default の稠密ラッパーは次元不一致のメッセージとともに中断します。実装は、両辺が定義されるところでは常に次を満たさなければなりません。

$$(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A + B)C = AC + BC ,$$

さらにスカラーが可換なら $(AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}$ も満たします。

この例は、すべての演算が全域的になる固定の $1 \times 1$ 型にすべての行列レベルを実装し、汎用の Gram 行列ヘルパーを使います。

///|
struct AlgApiScalarMatrix {
  value : Int
}

///|
impl @algebra.MatrixShape for AlgApiScalarMatrix with fn shape(_) {
  (1, 1)
}

///|
impl @algebra.TransposeMatrix for AlgApiScalarMatrix with fn transpose(self) {
  self
}

///|
impl Add for AlgApiScalarMatrix with fn add(left, right) {
  { value: left.value + right.value, }
}

///|
impl Neg for AlgApiScalarMatrix with fn neg(value) {
  { value: -value.value, }
}

///|
impl Sub for AlgApiScalarMatrix with fn sub(left, right) {
  left + -right
}

///|
impl Mul for AlgApiScalarMatrix with fn mul(left, right) {
  { value: left.value * right.value, }
}

///|
impl @algebra.AdditiveMatrix for AlgApiScalarMatrix

///|
impl @algebra.MatMulMatrix for AlgApiScalarMatrix

///|
fn[M : @algebra.MatMulMatrix] alg_api_gram(matrix : M) -> M {
  @algebra.TransposeMatrix::transpose(matrix) * matrix
}

///|
test "matrix traits compose" {
  let a : AlgApiScalarMatrix = { value: 3, }
  let b : AlgApiScalarMatrix = { value: 5, }
  inspect((a + b).value, content="8")
  inspect(alg_api_gram(a).value, content="9")
}

このリポジトリにおける実装

型	trait
@default.DenseVector[T]	VectorShape、T : Add + Neg のとき AdditiveVector、T : Add + Neg + Mul のとき VecMulVector
@default.ImmutableDenseVector[T]	DenseVector と同じ
@default.DenseMatrix[T]	MatrixShape、TransposeMatrix、T : Add + Neg のとき AdditiveMatrix、T : Add + Neg + AddMonoid + Mul のとき MatMulMatrix
@default.ImmutableDenseMatrix[T]	MatrixShape、TransposeMatrix、T : Add + Neg のとき AdditiveMatrix、T : Add + Neg + Zero + Mul のとき MatMulMatrix

具体型 @immut と @mutable はこれらの trait を直接は実装しません。各パッケージが自身の依存方向を保てるよう、backends/default で包まれています（アーキテクチャガイド を参照）。