multi_dot, matrix_power, dan slogdet

Tiga pekerjaan muncul begitu komputasi matriks mulai bertumbuh: mengalikan banyak matriks sekaligus, memangkatkan satu matriks berkali-kali, dan menghitung determinan yang nilainya melampaui jangkauan float64. NumPy menyediakan satu fungsi khusus untuk masing-masing: np.linalg.multi_dot, np.linalg.matrix_power, dan np.linalg.slogdet.

Perkalian matriks bersifat asosiatif — (A @ B) @ C menghasilkan nilai yang sama dengan A @ (B @ C). Tetapi kesetaraan nilai tidak berarti kesetaraan biaya: urutan pengerjaan mengubah jumlah operasi skalar secara besar. Pada rantai transformasi bertahap atau perkalian matriks transisi berulang, memilih urutan yang salah membuat komputasi menjadi jauh lebih lambat.

Urutan Optimal dengan multi_dot #

np.linalg.multi_dot([A, B, C, D]) menerima daftar matriks dan mengalikannya dalam urutan yang dihitung paling murah — fungsi ini menilai terlebih dahulu susunan tanda kurung mana yang paling hemat operasi, alih-alih mengerjakan kiri-ke-kanan secara paksa:

import numpy as np

rng = np.random.default_rng(42)
A = rng.random((2, 50))
B = rng.random((50, 2))
C = rng.random((2, 50))
D = rng.random((50, 2))
print("bentuk:", A.shape, B.shape, C.shape, D.shape)
R = np.linalg.multi_dot([A, B, C, D])
print("hasil multi_dot :", R.shape)
print("sama dgn A@B@C@D:", np.allclose(R, A @ B @ C @ D))
print("sama dgn np.dot berantai:", np.allclose(R, np.dot(np.dot(np.dot(A, B), C), D)))

Output yang Dihasilkan:

bentuk: (2, 50) (50, 2) (2, 50) (50, 2)
hasil multi_dot : (2, 2)
sama dgn A@B@C@D: True
sama dgn np.dot berantai: True

Bedah baris demi baris:

1. Baris 3-6 (rng dan empat matriks): empat matriks kecil berukuran berselang-seling lebar-sempit, dibuat dari generator ber-seed sehingga output pasti sama.
2. Baris 8 (R = ...): multi_dot mengembalikan array (2, 2) — bentuk akhir yang sama seperti perkalian berantai biasa.
3. Baris 9-10 (allclose): nilainya setara dengan A @ B @ C @ D maupun np.dot berantai dari bab Dot Product; yang berbeda hanya urutan pengerjaan di dalam fungsi.

Biaya tiap urutan (dihitung sebagai jumlah perkalian skalar) untuk bentuk di atas:

multi_dot memilih susunan termurah, 408: mengalikan (A @ B) dan (C @ D) lebih dulu agar hasil antara tetap kecil, lalu menggabungkannya. Penghematan terlihat kecil pada contoh 2x50 ini, tetapi skala dengan cepat pada matriks besar — dan multi_dot menghitung semuanya tanpa kita menyusun tanda kurung manual di atas operasi dasar bab Matrix Multiplication.

matrix_power: Menaikkan Matriks ke Pangkat #

np.linalg.matrix_power(A, n) menghasilkan A dikalikan dengan dirinya sendiri sebanyak n kali, dan menghitungnya lewat perkalian berulang yang hemat (pangkat dua berantai), bukan n kali perkalian sunyi:

import numpy as np

A = np.array([[1.0, 1.0],
              [0.0, 1.0]])
print("pangkat 0:")
print(np.linalg.matrix_power(A, 0))
print("pangkat 3:")
print(np.linalg.matrix_power(A, 3))
print("pangkat -1:")
print(np.linalg.matrix_power(A, -1))

Output yang Dihasilkan:

pangkat 0:
[[1. 0.]
 [0. 1.]]
pangkat 3:
[[1. 3.]
 [0. 1.]]
pangkat -1:
[[ 1. -1.]
 [ 0.  1.]]

1. Baris 3-4 (A): matriks segitiga atas sederhana yang mudah diperiksa dengan hitungan manual.
2. Baris 5-6 (pangkat 0): A^0 didefinisikan sebagai matriks identitas I — konsisten dengan konvensi pangkat bilangan.
3. Baris 7-8 (pangkat 3): hasilnya [[1, 3], [0, 1]], cocok dengan perkalian manual A @ A @ A: entri kanan atas bertambah satu setiap pangkat.
4. Baris 9-10 (pangkat -1): pangkat negatif berarti inverse dipangkatkan; matrix_power(A, -1) setara dengan np.linalg.inv(A) dari bab Inverse Matriks, dan pangkat -2 setara dengan inv(A) @ inv(A). Matriks singular akan memunculkan LinAlgError untuk pangkat negatif.

Matriks Transisi: Rute Dua Langkah #

Kasus nyata yang paling alami untuk pangkat matriks adalah graf. Bayangkan jaringan kurir dengan tiga kota — Jakarta, Bandung, Semarang — yang terhubung jalur langsung dua arah. Matriks ketetanggaan T berisi 1 bila ada jalur langsung antar dua kota, dan pangkat matriksnya menghitung banyaknya rute dua langkah:

import numpy as np

T = np.array([[0, 1, 1],
              [1, 0, 1],
              [1, 1, 0]])
T2 = np.linalg.matrix_power(T, 2)
print(T2)
print("jakarta -> jakarta (2 leg):", T2[0, 0])
print("jakarta -> bandung (2 leg):", T2[0, 1])

Output yang Dihasilkan:

[[2 1 1]
 [1 2 1]
 [1 1 2]]
jakarta -> jakarta (2 leg): 2
jakarta -> bandung (2 leg): 1

1. Baris 7 (T2 = ...): entri (i, j) dari T @ T menghitung banyak kota perantara yang menghubungkan i ke j; matrix_power merapikan penulisannya.
2. Baris 9 (T2[0, 0]): rute dua leg Jakarta ke Jakarta ada 2 — pulang lewat Bandung atau lewat Semarang.
3. Baris 10 (T2[0, 1]): Jakarta ke Bandung dalam dua leg hanya lewat Semarang, sehingga bernilai 1.

Pola yang sama berlaku untuk matriks transisi probabilitas (random walk, peringkat halaman web): pangkat ke-n memproyeksikan sistem n langkah ke depan.

slogdet: Log-Determinan Aman Overflow #

Determinan matriks diagonal adalah perkalian entri diagonalnya (bab Determinant). Untuk matriks 400x400 dengan entri diagonal 1000, determinannya adalah 1000^400 = 10^1200 — jauh di atas batas float64 sekitar 1.8e308. Fungsi np.linalg.slogdet menghindari masalah ini dengan mengembalikan tanda dan logaritma determinan:

import numpy as np

A = np.diag([1000.0] * 400)
try:
    with np.errstate(over="raise"):
        d = np.linalg.det(A)
    print("det    :", d)
except FloatingPointError as e:
    print("det -> FloatingPointError:", e)
sign, logabsdet = np.linalg.slogdet(A)
print("sign   :", sign)
print("logabs :", logabsdet)
with np.errstate(over="ignore"):
    print("det ulang (exp) :", sign * np.exp(logabsdet))

Output yang Dihasilkan:

det -> FloatingPointError: overflow encountered in det
sign   : 1.0
logabs : 2763.102111592873
det ulang (exp) : inf

1. Baris 3 (A): matriks diagonal 400x400, seluruh entri diagonal 1000 — contoh determinan besar yang sepenuhnya deterministik.
2. Baris 5-10 (det dalam errstate): np.errstate(over="raise") mengubah pelaporan luapan menjadi exception, sehingga det melempar FloatingPointError yang kita tangkap dan cetak. Tanpa errstate, fungsi mengembalikan inf disertai RuntimeWarning.
3. Baris 11-13 (slogdet): hasilnya pasangan (sign, logabsdet) — tanda determinan (1.0, positif) dan logaritma natural nilai mutlaknya, sekitar 2763.102. Angka sekecil ini aman tersimpan di float64.
4. Baris 14-15 (exp): mengembalikan nilai asli lewat sign * exp(logabsdet) menghasilkan inf lagi. Ini bukan kegagalan slogdet, melainkan bukti bahwa determinan aslinya memang di luar jangkauan float64.

Nilai 10^1200 di atas adalah kasus ekstrem yang sengaja dibuat; kasus riil — matriks kovarians berdimensi besar, produk likelihood bertumpuk — meluap jauh lebih cepat dari yang kita duga, dan slogdet adalah jawaban standarnya.