Linear Algebra — রূপান্তরের ভাষা

আগে এটা বুঝি

Level 0-এর বাকি সব লেসন discrete জিনিস নিয়ে ছিল — set, graph, সংখ্যা, সত্য-মিথ্যা। Linear algebra আপাতদৃষ্টিতে অন্য জগতের।

তবু এটা এখানে আছে, কারণ CS-এর কয়েকটা সবচেয়ে গুরুত্বপূর্ণ ক্ষেত্র পুরোপুরি এর উপর দাঁড়ানো:

আপনার screen-এর প্রতিটা pixel একটা matrix গুণের ফল
Google-এর PageRank একটা eigenvector
প্রতিটা neural network পর্যায়ক্রমে matrix গুণ আর non-linearity
Vector database-এ “similar” খোঁজা মানে dot product
GPU নামের যন্ত্রটাই আসলে matrix গুণের জন্য বানানো

কিন্তু এই লেসনটা গণিতের ডিগ্রির অধ্যায় নয়। একটা কেন্দ্রীয় ধারণার চারপাশে সবকিছু সাজানো:

একটা matrix হলো একটা function। নির্দিষ্ট করে বললে, একটা linear function। আর matrix গুণ হলো function composition।

Functions-এর লেসনে আমরা composition, injectivity আর invertibility শিখেছি। সেগুলো এখানে হুবহু ফিরে আসবে — শুধু সংখ্যার পোশাকে। Determinant শূন্য মানে injective নয়। Inverse আছে মানে bijective। Rank মানে কতটা মাত্রা টিকে থাকল।

মূল ধারণা

Vector — তিনটা ভিন্ন পাঠ

একটা vector [3, 4] কে তিনভাবে পড়া যায়, আর তিনটাই কাজে লাগে:

পাঠ	অর্থ	কোথায়
বিন্দু	সমতলে `(3,4)` অবস্থান	graphics, geometry
দিক	origin থেকে একটা তীর	পদার্থবিজ্ঞান, animation
ডেটা	দুইটা সংখ্যার তালিকা	ML, search, database

তৃতীয়টাই CS-এ সবচেয়ে বেশি ব্যবহৃত, আর সবচেয়ে কম শেখানো হয়।

pixel     = [255, 128, 0]              # RGB
user      = [age, income, clicks]      # feature vector
sentence  = [0.12, -0.45, ..., 0.03]   # embedding, 768 মাত্রা

একটা ৭৬৮-মাত্রার vector-কে “কল্পনা” করার দরকার নেই। যা দরকার তা হলো: এটা একটা সংখ্যার তালিকা, আর তালিকাগুলোর মধ্যে দূরত্ব ও কোণ মাপা যায়।

Dot product — একটামাত্র সংখ্যা, বিশাল কাজ

$\mathbf{a} \cdot \mathbf{b} = \sum_i a_i b_i = |\mathbf{a}|\,|\mathbf{b}|\cos\theta$

দুইটা সংজ্ঞা, একই ফল — আর দ্বিতীয়টাই অর্থ দেয়।

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

জ্যামিতিক পাঠ:

`a · b`	কোণ	মানে
বড় ধনাত্মক	~0°	একই দিকে
শূন্য	90°	লম্ব, সম্পর্কহীন
ঋণাত্মক	>90°	বিপরীত দিকে

Cosine similarity — search আর recommendation-এর ইঞ্জিন

Dot product দৈর্ঘ্যের উপর নির্ভর করে, যা প্রায়ই অবাঞ্ছিত। একটা লম্বা document-এর সব সংখ্যা বড়, তাই তার dot product সবসময় বড় — কিন্তু সেটা মিলের প্রমাণ নয়।

দৈর্ঘ্য বাদ দিন:

$\text{sim}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a}\cdot\mathbf{b}}{|\mathbf{a}|\,|\mathbf{b}|} = \cos\theta \in [-1, 1]$

import math

def cosine(a, b):
    num = sum(x*y for x, y in zip(a, b))
    den = math.sqrt(sum(x*x for x in a)) * math.sqrt(sum(y*y for y in b))
    return num / den if den else 0.0

প্রতিটা semantic search এটাই করছে

আপনি যখন একটা vector database-এ (Pinecone, Weaviate, pgvector) query করেন, ভেতরে যা হয়:

আপনার query একটা embedding vector-এ রূপান্তরিত হয়
Database সংরক্ষিত প্রতিটা vector-এর সাথে cosine similarity মাপে
সবচেয়ে বেশি similarity-র k টা ফেরত দেয়

পুরো “semantic search” জিনিসটা — একটা dot product আর দুইটা বর্গমূল, লক্ষ লক্ষবার।

আর সেজন্যই এই operation-টা এত optimize করা হয়েছে: SIMD, GPU, quantisation, আর approximate nearest neighbour index (HNSW, IVF)। Level 11-এ আমরা এই optimization গুলো দেখব।

Matrix = function

এখানেই মূল ধারণাটা।

একটা m × n matrix A একটা function:

$A : \mathbb{R}^n \to \mathbb{R}^m, \qquad \mathbf{x} \mapsto A\mathbf{x}$

Linear মানে দুইটা শর্ত মানে:

$A(\mathbf{x} + \mathbf{y}) = A\mathbf{x} + A\mathbf{y}, \qquad A(c\mathbf{x}) = c\,A\mathbf{x}$

সহজ ভাষায়: সরলরেখা সরলরেখাই থাকে, origin origin-এই থাকে।

কীভাবে পড়বেন একটা matrix: প্রতিটা কলাম বলে দেয় একটা basis vector কোথায় যায়।

$A = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$

প্রথম কলাম [0,1] → x-অক্ষের [1,0] চলে গেল [0,1]-এ
দ্বিতীয় কলাম [-1,0] → y-অক্ষের [0,1] চলে গেল [-1,0]-এ

দুইটা অক্ষই ৯০° ঘুরল — এটা একটা rotation matrix।

সাধারণ 2D রূপান্তর:

Identity        Scale 2x         Rotate 90°       Shear
[1  0]          [2  0]           [0 -1]           [1  1]
[0  1]          [0  2]           [1  0]           [0  1]

 ↑               ↑                 ←                ↑ ↗
 └→              └──→              ↑                └──→

প্রতিটা কলাম একটা basis vector-এর গন্তব্য। এটুকু জানলেই যেকোনো matrix পড়া যায়।

Matrix গুণ = composition

$(AB)\mathbf{x} = A(B\mathbf{x})$

B আগে প্রয়োগ হয়, তারপর A — ঠিক f(g(x))-এর মতো, ডান থেকে বামে পড়তে হয়।

এই একটা তথ্য থেকে দুইটা ধর্ম সরাসরি বেরিয়ে আসে:

Associative — (AB)C = A(BC), কারণ composition associative।

Commutative নয় — AB ≠ BA, কারণ f∘g ≠ g∘f।

কেন commutativity ভাঙে — একটা বাস্তব উদাহরণ

আগে ঘুরিয়ে তারপর সরানো, আর আগে সরিয়ে তারপর ঘোরানো — সম্পূর্ণ ভিন্ন ফল।

ঘুরিয়ে-তারপর-সরানো:   বস্তু নিজের জায়গায় ঘুরল, তারপর সরল
সরিয়ে-তারপর-ঘোরানো:   বস্তু সরল, তারপর origin-এর চারপাশে ঘুরল
                        — অনেক দূরে চলে গেল

3D graphics-এ transformation-এর ক্রম ভুল হওয়াটা সবচেয়ে সাধারণ bug। OpenGL/Vulkan-এর matrix stack-এ ক্রম উল্টো মনে হয়, কারণ M = T · R · S লিখলে S আগে প্রয়োগ হয়।

Functions-এর লেসনের (g∘f)⁻¹ = f⁻¹∘g⁻¹ নিয়মটাও এখানে হুবহু:

$(AB)^{-1} = B^{-1}A^{-1}$

Determinant — তথ্য হারাচ্ছে কি না

Determinant একটা সংখ্যা যা বলে রূপান্তরটা আয়তন কতগুণ করে।

$\det\begin{bmatrix} a & b \\ c & d \end{bmatrix} = ad - bc$

`det`	মানে
`2`	আয়তন দ্বিগুণ হলো
`1`	আয়তন অপরিবর্তিত (rotation)
`−1`	আয়তন একই, কিন্তু orientation উল্টে গেল
`0`	আয়তন শূন্য হয়ে গেল — মাত্রা ধসে পড়ল

শেষ সারিটাই সবচেয়ে গুরুত্বপূর্ণ, আর এখানেই functions-এর লেসনের সাথে সংযোগ।

det = 0 মানে পুরো space একটা নিম্নমাত্রিক জিনিসে চেপে গেছে — 2D সমতল একটা রেখায়, বা 3D স্থান একটা সমতলে।

আর তখন অসংখ্য ভিন্ন input একই output দেয় — অর্থাৎ function-টা injective নয়, তথ্য হারিয়ে গেছে, inverse নেই।

det ≠ 0                          det = 0

  ↑                                ↑
  │  ┌────┐        ┌──────┐        │
  │  │    │   →    │      │        │  ●───────────
  │  └────┘        └──────┘        │   (সব বিন্দু একটা রেখায়)
  └────────→       └────────→      └────────→

  আয়তন টিকে আছে                   আয়তন শূন্য
  উল্টানো যায়                      উল্টানো যায় না

det = 0 মানে function-টা injective নয় — ঠিক যেমন hash function বা lossy compression।

Rank হলো এর পরিমাণগত রূপ — output-এ কত মাত্রা টিকে থাকল। n × n matrix-এ rank = n মানে full rank, det ≠ 0, invertible। rank < n মানে মাত্রা হারিয়েছে।

Eigenvector — যে দিকগুলো ঘোরে না

বেশিরভাগ vector একটা রূপান্তরে দিক বদলায়। কিছু বদলায় না — শুধু লম্বা বা খাটো হয়।

$A\mathbf{v} = \lambda \mathbf{v}$

v হলো eigenvector, λ হলো তার eigenvalue।

একটা rotation matrix-এ (2D-তে) কোনো বাস্তব eigenvector নেই — সব দিকই ঘোরে। একটা scaling matrix-এ প্রতিটা দিকই eigenvector।

কেন CS-এ এটা লাগে: একটা রূপান্তর বারবার প্রয়োগ করলে (Aᵏx) কী হয়? সবচেয়ে বড় eigenvalue-র দিকটাই শেষে প্রাধান্য পায় — বাকি সব দিক তুলনায় মিলিয়ে যায়।

এটাই power iteration, আর এটাই PageRank।

ভেতরে কী ঘটছে

PageRank = dominant eigenvector

Graph theory-র লেসনে দেখেছি adjacency matrix M-এর Mᵏ বলে k-দৈর্ঘ্যের path সংখ্যা। PageRank সেই ধারণারই probabilistic রূপ।

মডেল: একজন random surfer লিংক ধরে ঘুরছে। দীর্ঘকাল পরে সে কোন page-এ থাকার সম্ভাবনা কত?

M কে column-stochastic transition matrix বানান — Mᵢⱼ = page j থেকে page i-তে যাওয়ার সম্ভাবনা।

$\mathbf{r}_{k+1} = M\mathbf{r}_k$

স্থিতিশীল অবস্থায়:

$M\mathbf{r} = \mathbf{r} \qquad \text{অর্থাৎ } \lambda = 1 \text{-এর eigenvector}$

PageRank আক্ষরিকভাবে একটা eigenvector।

def pagerank(M, n, damping=0.85, iters=100):
    r = [1.0 / n] * n
    for _ in range(iters):
        new = [(1 - damping) / n] * n
        for j in range(n):
            for i in range(n):
                new[i] += damping * M[i][j] * r[j]
        r = new
    return r

Damping factor (0.85) দুইটা সমস্যা সমাধান করে: dangling node (যার কোনো outgoing link নেই) আর disconnected component। এটা নিশ্চিত করে matrix-টা irreducible, তাই অনন্য stationary distribution আছে (Perron–Frobenius theorem)।

ইতিহাস

Larry Page আর Sergey Brin-এর ১৯৯৮-এর পেপারে PageRank-এর মূল অন্তর্দৃষ্টি ছিল: একটা page-এর গুরুত্ব নির্ভর করে কারা তাকে লিংক করেছে তার উপর, আর সেই লিংককারীদের গুরুত্বের উপর।

এটা একটা recursive সংজ্ঞা — আর recursive সংজ্ঞার fixed point বের করা মানেই eigenvector খোঁজা।

গণিতটা নতুন ছিল না (Markov chain ১৯০৬ থেকে)। নতুন ছিল প্রয়োগটা — আর সেটাই একটা ট্রিলিয়ন-ডলার কোম্পানি বানিয়েছে।

Neural network — কেন non-linearity ছাড়া চলে না

একটা neural network layer:

$\mathbf{h} = \sigma(W\mathbf{x} + \mathbf{b})$

W একটা matrix, σ একটা non-linear function (ReLU, sigmoid)।

σ বাদ দিলে কী হয়?

h₁ = W₁x
h₂ = W₂h₁ = W₂W₁x
h₃ = W₃h₂ = W₃W₂W₁x

কিন্তু W₃W₂W₁ নিজেই একটা matrix! ধরুন W = W₃W₂W₁, তাহলে:

$\mathbf{h}_3 = W\mathbf{x}$

একশো layer-এর network একটামাত্র layer-এর সমান।

কারণ linear map-দের composition আবার linear — এটা functions-এর লেসনের composition ধর্মের সরাসরি পরিণতি।

Homogeneous coordinates — translation-কে matrix বানানো

একটা সমস্যা: translation linear নয়। x → x + t origin-কে সরিয়ে দেয়, তাই এটা কোনো matrix দিয়ে প্রকাশ করা যায় না।

কিন্তু graphics pipeline-এ সব রূপান্তর একই রকম হওয়া দরকার, যাতে সেগুলো compose করা যায়।

সমাধান — একটা বাড়তি মাত্রা যোগ করুন:

$\begin{bmatrix} x' \\ y' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & t_x \\ 0 & 1 & t_y \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ 1 \end{bmatrix} = \begin{bmatrix} x + t_x \\ y + t_y \\ 1 \end{bmatrix}$

3D-তে এটাই 4×4 matrix। এখন translation, rotation, scaling, projection — সবই matrix, তাই সবগুলো একটা matrix-এ গুণ করে রাখা যায়।

একটা vertex screen-এ পৌঁছানো পর্যন্ত

Model matrixবস্তুর নিজের স্থানাঙ্ক → world
View matrixworld → camera-র দৃষ্টিকোণ
Projection matrixcamera → clip space (perspective)
MVP = P · V · Mতিনটা একটা matrix-এ গুণ করে রাখা
GPU vertex shaderপ্রতিটা vertex-এ একটা 4×4 গুণ
Perspective dividew দিয়ে ভাগ — এখানেই দূরের জিনিস ছোট হয়
Screen pixelviewport transform

লক্ষ্য করুন: লক্ষ লক্ষ vertex, কিন্তু CPU একবারই P·V·M হিসাব করে GPU-কে পাঠায়। GPU প্রতিটা vertex-এ শুধু একটা 4×4 × 4×1 গুণ করে।

এটাই কেন GPU-র hardware সরাসরি 4×4 matrix গুণের জন্য optimize করা — আর কেন সেই একই hardware পরে deep learning-এ কাজে লেগে গেল।

Memory layout — যেখানে গণিত hardware-এ ধাক্কা খায়

গাণিতিকভাবে matrix একটা 2D জিনিস। Memory একমাত্রিক। তাই একটা mapping লাগে।

Row-major (C, C++, Python/NumPy default):
  A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] ...

Column-major (Fortran, MATLAB, OpenGL):
  A[0][0] A[1][0] A[0][1] A[1][1] ...

কেন এটা গুরুত্বপূর্ণ: cache একবারে একটা পুরো cache line (সাধারণত ৬৪ byte = ৮টা double) নিয়ে আসে। পরপর memory পড়লে প্রায় সব hit; লাফিয়ে পড়লে প্রায় সব miss।

Naive matrix multiply-এর তিনটা nested loop — ক্রম বদলালে গাণিতিক ফল একই, FLOP সংখ্যা একই, কিন্তু সময় ৩–১০ গুণ আলাদা।

/* ijk — k সবচেয়ে ভেতরে: B[k][j] কলাম ধরে লাফায় → cache miss */
for (i) for (j) for (k) C[i][j] += A[i][k] * B[k][j];

/* ikj — j সবচেয়ে ভেতরে: B[k][j] আর C[i][j] দুটোই সারি ধরে → hit */
for (i) for (k) for (j) C[i][j] += A[i][k] * B[k][j];

নিচের experiment-এ আমরা এটা মেপে দেখব।

উদাহরণ

Embedding আর similarity — একটা সম্পূর্ণ উদাহরণ

ধরুন তিনটা বাক্যের bag-of-words vector বানাই:

শব্দভাণ্ডার: [database, index, query, cat, dog, pet]

s1 = "database index query"     → [1, 1, 1, 0, 0, 0]
s2 = "query database"           → [1, 0, 1, 0, 0, 0]
s3 = "cat dog pet"              → [0, 0, 0, 1, 1, 1]

Cosine similarity:

$\text{sim}(s_1, s_2) = \frac{1\cdot1 + 1\cdot0 + 1\cdot1}{\sqrt{3}\cdot\sqrt{2}} = \frac{2}{2.449} = 0.816$

$\text{sim}(s_1, s_3) = \frac{0}{\sqrt{3}\cdot\sqrt{3}} = 0$

s1 আর s2 খুব কাছাকাছি (দুটোই database নিয়ে), s1 আর s3 সম্পূর্ণ লম্ব (কোনো শব্দ মেলে না)।

Bag-of-words-এর সীমা: “cat” আর “kitten”-এর similarity শূন্য, যদিও অর্থে কাছাকাছি। আর শব্দের ক্রম হারিয়ে যায় — “dog bites man” আর “man bites dog” অভিন্ন vector।

Embedding সেটা ঠিক করে: একটা neural network প্রতিটা শব্দকে (বা বাক্যকে) এমন একটা ঘন vector-এ map করে যেখানে অর্থগত মিল জ্যামিতিক নৈকট্য হয়ে যায়।

"cat"    → [ 0.21, -0.43, 0.88, ... ]    768 মাত্রা
"kitten" → [ 0.19, -0.41, 0.85, ... ]    কাছাকাছি
"server" → [-0.62,  0.11, 0.03, ... ]    দূরে

কিন্তু similarity মাপার গণিতটা অপরিবর্তিত — সেই একই cosine। শুধু vector-গুলো আরো ভালো।

Determinant শূন্য — একটা বাস্তব সমস্যা

3D graphics-এ একটা সাধারণ bug: একটা object-কে একটা অক্ষে 0 দিয়ে scale করা।

$S = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \qquad \det S = 0$

পুরো 3D object একটা সমতলে চ্যাপ্টা হয়ে গেল। আর যেহেতু det = 0, inverse নেই — আপনি আর ফিরে আসতে পারবেন না।

আরো খারাপ: normal vector হিসাব করতে inverse transpose লাগে, তাই lighting সম্পূর্ণ ভেঙে পড়বে (division by zero, NaN, কালো বা সাদা texture)।

একই জিনিস linear system-এ:

2x + 4y = 10
 x + 2y = 5

$\det\begin{bmatrix} 2 & 4 \\ 1 & 2 \end{bmatrix} = 4 - 4 = 0$

দ্বিতীয় সমীকরণ প্রথমটার অর্ধেক — কোনো নতুন তথ্য নেই। অসীম সংখ্যক সমাধান।

আর ডান পাশ যদি সঙ্গতিপূর্ণ না হতো (2x+4y=10, x+2y=6), তাহলে কোনো সমাধানই নেই।

নিজে চালিয়ে দেখুন

EXPERIMENT

Cosine similarity নিজে চালিয়ে দেখুন

Python 3 (কোনো library লাগবে না)· ১০ মিনিট

import math
from collections import Counter

def vectorize(text, vocab):
    counts = Counter(text.lower().split())
    return [counts.get(w, 0) for w in vocab]

def cosine(a, b):
    num = sum(x*y for x, y in zip(a, b))
    da = math.sqrt(sum(x*x for x in a))
    db = math.sqrt(sum(y*y for y in b))
    return num / (da * db) if da and db else 0.0


docs = [
    "database index query optimization",
    "query the database for records",
    "index scan versus sequential scan",
    "cat dog pet animal",
    "my pet cat likes the dog",
]

vocab = sorted({w for d in docs for w in d.lower().split()})
vecs = [vectorize(d, vocab) for d in docs]

print(f"শব্দভাণ্ডার আকার: {len(vocab)}\n")
print("similarity matrix:")
print("      " + "  ".join(f"d{j}" for j in range(len(docs))))
for i, a in enumerate(vecs):
    row = "  ".join(f"{cosine(a, b):.2f}" for b in vecs)
    print(f"  d{i}  {row}")

print("\nপ্রতিটা doc-এর সবচেয়ে কাছের প্রতিবেশী:")
for i, a in enumerate(vecs):
    best = max((j for j in range(len(docs)) if j != i),
               key=lambda j: cosine(a, vecs[j]))
    print(f"  d{i} ({docs[i][:30]:30s}) → d{best}  "
          f"sim={cosine(a, vecs[best]):.3f}")

প্রত্যাশিত ফল:

similarity matrix:
      d0    d1    d2    d3    d4
  d0  1.00  0.50  0.25  0.00  0.00
  d1  0.50  1.00  0.00  0.00  0.18
  d2  0.25  0.00  1.00  0.00  0.00
  d3  0.00  0.00  0.00  1.00  0.67
  d4  0.00  0.18  0.00  0.67  1.00

লক্ষ্য করুন দুইটা স্পষ্ট গুচ্ছ তৈরি হয়েছে — database-বিষয়ক (d0, d1, d2) আর পশু-বিষয়ক (d3, d4)। কোনো ML নেই, শুধু জ্যামিতি।

আর d1–d4-এর 0.18 এসেছে শুধু “the” শব্দটা মেলার কারণে — এটাই কেন বাস্তবে stop word বাদ দেওয়া হয়, আর কেন TF-IDF দিয়ে বিরল শব্দকে বেশি ওজন দেওয়া হয়।

নিজে চেষ্টা করুন: docs তালিকায় নিজের বাক্য যোগ করুন, আর “the”, “for”, “my” বাদ দিয়ে আবার চালান — matrix কতটা পরিষ্কার হয়?

এটা কী প্রমাণ করে

Semantic search-এর ভেতরের গণিতটা আসলে একটা dot product আর দুইটা বর্গমূল — আর সেটা কয়েক লাইনে লেখা যায়।

EXPERIMENT

Loop order বদলে ৩ গুণ গতি — একই FLOP-এ

Python 3, বা C (gcc)· ১৫ মিনিট

import time, random

def make(n):
    return [[random.random() for _ in range(n)] for _ in range(n)]

def mul_ijk(A, B, n):
    C = [[0.0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            s = 0.0
            for k in range(n):
                s += A[i][k] * B[k][j]      # B কলাম ধরে লাফায়
            C[i][j] = s
    return C

def mul_ikj(A, B, n):
    C = [[0.0]*n for _ in range(n)]
    for i in range(n):
        Ai, Ci = A[i], C[i]
        for k in range(n):
            a = Ai[k]
            Bk = B[k]
            for j in range(n):
                Ci[j] += a * Bk[j]          # B আর C দুটোই সারি ধরে
    return C


n = 200
A, B = make(n), make(n)

for name, fn in [("ijk", mul_ijk), ("ikj", mul_ikj)]:
    t0 = time.perf_counter()
    fn(A, B, n)
    dt = time.perf_counter() - t0
    flops = 2 * n**3
    print(f"{name}: {dt:6.2f} s   {flops/dt/1e6:7.1f} MFLOP/s")

সাধারণ ফলাফল:

ijk:   4.85 s     3.3 MFLOP/s
ikj:   2.91 s     5.5 MFLOP/s

C-তে পার্থক্য অনেক বড়, কারণ Python-এর interpreter overhead memory effect ঢেকে দেয়:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 512

static double A[N][N], B[N][N], C[N][N];

void ijk(void) {
    for (int i = 0; i \< N; i++)
      for (int j = 0; j \< N; j++) {
        double s = 0;
        for (int k = 0; k \< N; k++) s += A[i][k] * B[k][j];
        C[i][j] = s;
      }
}
void ikj(void) {
    for (int i = 0; i \< N; i++)
      for (int k = 0; k \< N; k++) {
        double a = A[i][k];
        for (int j = 0; j \< N; j++) C[i][j] += a * B[k][j];
      }
}
double bench(void (*f)(void), const char *name) {
    for (int i = 0; i \< N; i++) for (int j = 0; j \< N; j++) C[i][j] = 0;
    clock_t t = clock(); f();
    double dt = (double)(clock() - t) / CLOCKS_PER_SEC;
    printf("%-4s %6.3f s   %7.1f MFLOP/s\n", name, dt, 2.0*N*N*N/dt/1e6);
    return dt;
}
int main(void) {
    for (int i = 0; i \< N; i++) for (int j = 0; j \< N; j++)
        { A[i][j] = rand()/(double)RAND_MAX; B[i][j] = rand()/(double)RAND_MAX; }
    bench(ijk, "ijk");
    bench(ikj, "ikj");
    return 0;
}

gcc -O2 -o mm mm.c && ./mm

সাধারণ ফলাফল:

ijk   0.421 s     637.6 MFLOP/s
ikj   0.128 s    2097.2 MFLOP/s

৩.৩ গুণ দ্রুত — অথচ গুণ-যোগের সংখ্যা হুবহু 2N³, দুই ক্ষেত্রেই।

কেন: ijk-তে ভেতরের loop B[k][j] পড়ে, যেখানে k বাড়ছে — অর্থাৎ B-এর একটা কলাম ধরে লাফানো। Row-major layout-এ পরপর দুইটা মানের মধ্যে N × 8 = 4096 byte দূরত্ব। প্রতিটা access একটা নতুন cache line, তাই প্রায় প্রতিবারই miss।

ikj-তে ভেতরের loop B[k][j] আর C[i][j] — দুটোই j বাড়িয়ে, অর্থাৎ পরপর memory। একটা cache line-এ ৮টা double, তাই ৮টার মধ্যে ৭টা hit। উপরন্তু hardware prefetcher pattern চিনে আগেই ডেটা এনে রাখে।

টিপ

perf দিয়ে সরাসরি cache miss গুনতে পারেন:

perf stat -e cache-misses,cache-references ./mm

Level 3-এ আমরা cache-এর গঠন দেখব, আর Level 11-এ tiling ও SIMD দিয়ে এই একই গুণকে আরো ১০ গুণ দ্রুত করব।

আর এই কারণেই কেউ নিজে matrix multiply লেখে না — BLAS (OpenBLAS, MKL) দশকের optimization ধারণ করে, আর একই hardware-এ naive কোডের চেয়ে ৫০–১০০ গুণ দ্রুত।

এটা কী প্রমাণ করে

Big-O একই, গুণ-যোগের সংখ্যা হুবহু একই — তবু সময় কয়েক গুণ আলাদা। পার্থক্যটা পুরোপুরি memory access pattern-এর, arithmetic-এর নয়।

নিজে বানান

BUILD IT

Linear Algebra শূন্য থেকে — numpy ছাড়া

Python · ●●●○○

Vector operation — যোগ, scalar গুণ, dot, norm, cosine
Matrix — গুণ, transpose, identity, determinant
Composition associative কিন্তু commutative নয় — কোডে যাচাই করুন
2D রূপান্তর প্রয়োগ করে বিন্দু ঘোরান ও সরান
Power iteration দিয়ে dominant eigenvector, তারপর PageRank

import math

# ── Vector ───────────────────────────────────────────────────
def vadd(a, b):     return [x + y for x, y in zip(a, b)]
def vscale(c, a):   return [c * x for x in a]
def dot(a, b):      return sum(x * y for x, y in zip(a, b))
def norm(a):        return math.sqrt(dot(a, a))

def cosine(a, b):
    d = norm(a) * norm(b)
    return dot(a, b) / d if d else 0.0


# ── Matrix ───────────────────────────────────────────────────
def shape(A):       return len(A), len(A[0])
def transpose(A):   return [list(col) for col in zip(*A)]
def identity(n):    return [[1.0 if i == j else 0.0 for j in range(n)]
                            for i in range(n)]

def matmul(A, B):
    n, m = shape(A)
    m2, p = shape(B)
    assert m == m2, f"আকার মেলে না: {shape(A)} × {shape(B)}"
    Bt = transpose(B)                       # cache-friendly
    return [[dot(row, col) for col in Bt] for row in A]

def matvec(A, x):
    return [dot(row, x) for row in A]

def det(A):
    n, m = shape(A)
    assert n == m, "determinant শুধু square matrix-এ"
    if n == 1: return A[0][0]
    if n == 2: return A[0][0]*A[1][1] - A[0][1]*A[1][0]
    total = 0.0
    for j in range(n):                      # প্রথম সারি ধরে expansion
        minor = [row[:j] + row[j+1:] for row in A[1:]]
        total += ((-1) ** j) * A[0][j] * det(minor)
    return total


# ── 2D রূপান্তর (homogeneous coordinates) ────────────────────
def rotation(deg):
    t = math.radians(deg)
    return [[math.cos(t), -math.sin(t), 0],
            [math.sin(t),  math.cos(t), 0],
            [0,            0,           1]]

def translation(tx, ty):
    return [[1, 0, tx],
            [0, 1, ty],
            [0, 0, 1]]

def scaling(sx, sy):
    return [[sx, 0, 0],
            [0, sy, 0],
            [0,  0, 1]]

def apply(M, x, y):
    r = matvec(M, [x, y, 1])
    return round(r[0], 4), round(r[1], 4)


# ── composition-এর ধর্ম যাচাই ────────────────────────────────
R = rotation(90)
T = translation(5, 0)
S = scaling(2, 2)

print("── composition ─────────────────────────────")
print("ঘুরিয়ে-তারপর-সরানো  T·R  :", apply(matmul(T, R), 1, 0))
print("সরিয়ে-তারপর-ঘোরানো  R·T  :", apply(matmul(R, T), 1, 0))
print("  → একই নয়, তাই commutative নয়")

left  = matmul(matmul(T, R), S)
right = matmul(T, matmul(R, S))
same = all(abs(a-b) \< 1e-9 for r1, r2 in zip(left, right)
                            for a, b in zip(r1, r2))
print(f"associative (T·R)·S == T·(R·S) : {same}")


# ── determinant আর তথ্য হারানো ───────────────────────────────
print("\n── determinant ─────────────────────────────")
for name, M in [("identity", identity(3)),
                ("rotate 90", rotation(90)),
                ("scale 2x", scaling(2, 2)),
                ("collapse", [[1,0,0],[0,0,0],[0,0,1]])]:
    d = det(M)
    verdict = "invertible" if abs(d) > 1e-9 else "det=0 — তথ্য হারিয়েছে"
    print(f"  {name:12s} det = {d:7.3f}   {verdict}")


# ── Power iteration → dominant eigenvector ───────────────────
def power_iteration(A, iters=200):
    n = len(A)
    v = [1.0 / n] * n
    for _ in range(iters):
        v = matvec(A, v)
        m = norm(v)
        if m == 0: break
        v = vscale(1.0 / m, v)
    lam = dot(v, matvec(A, v)) / dot(v, v)      # Rayleigh quotient
    return lam, v

print("\n── eigenvector ─────────────────────────────")
A = [[2, 1],
     [1, 2]]
lam, v = power_iteration(A)
print(f"  dominant eigenvalue ≈ {lam:.4f}   (সঠিক: 3)")
print(f"  eigenvector ≈ [{v[0]:.4f}, {v[1]:.4f}]   (সঠিক দিক: [0.707, 0.707])")
print(f"  যাচাই Av ≈ λv : {[round(x,4) for x in matvec(A, v)]} vs "
      f"{[round(lam*x,4) for x in v]}")


# ── PageRank ─────────────────────────────────────────────────
def pagerank(links, damping=0.85, iters=200):
    """links: {page: [যেসব page-এ যায়]}"""
    pages = sorted(links)
    idx = {p: i for i, p in enumerate(pages)}
    n = len(pages)

    M = [[0.0]*n for _ in range(n)]
    for p, outs in links.items():
        if not outs:                                  # dangling node
            for i in range(n): M[i][idx[p]] = 1.0 / n
        else:
            for q in outs: M[idx[q]][idx[p]] = 1.0 / len(outs)

    r = [1.0 / n] * n
    for _ in range(iters):
        nxt = [(1 - damping) / n] * n
        for i in range(n):
            nxt[i] += damping * sum(M[i][j] * r[j] for j in range(n))
        r = nxt
    return dict(sorted(zip(pages, r), key=lambda kv: -kv[1]))

print("\n── PageRank ────────────────────────────────")
web = {
    "home":    ["about", "docs", "blog"],
    "about":   ["home"],
    "docs":    ["home", "api"],
    "api":     ["docs"],
    "blog":    ["home"],
    "orphan":  [],
}
for page, score in pagerank(web).items():
    bar = "█" * int(score * 100)
    print(f"  {page:8s} {score:.4f}  {bar}")

প্রত্যাশিত ফল — home সবচেয়ে উপরে, কারণ চারটা page তাকে লিংক করেছে, আর docs দ্বিতীয়, কারণ home (একটা উচ্চ-মানের page) তাকে লিংক করেছে।

নিজে বাড়ান:

inverse() লিখুন Gauss–Jordan elimination দিয়ে, আর A @ inverse(A) ≈ I যাচাই করুন
solve(A, b) লিখুন Gaussian elimination দিয়ে — আর দেখুন det = 0 হলে কী হয়
Condition number আনুমানিক বের করুন এবং একটা ill-conditioned matrix-এ inverse কতটা ভুল হয় মাপুন
Power iteration-কে deflation দিয়ে বাড়িয়ে দ্বিতীয় eigenvector বের করুন
matmul-এ tiling যোগ করুন (৩২×৩২ block) আর Python-এ কতটা লাভ হয় মাপুন
আপনার নিজের website-এর internal link graph দিয়ে PageRank চালান

বাস্তব সিস্টেমে

Linear algebra যেখানে যেখানে

Graphics pipeline। প্রতিটা frame-এ লক্ষ লক্ষ vertex একটা 4×4 MVP matrix দিয়ে গুণ হয়। GPU-র hardware আক্ষরিকভাবে এই operation-এর জন্য বানানো — আর সেই hardware পরে deep learning-এ কাজে লেগে গেছে।

Neural network। প্রতিটা layer একটা matrix গুণ। GPT-শ্রেণির model-এ প্রতিটা token-এর জন্য বিলিয়ন-প্যারামিটার matrix গুণ। Training-এর backpropagation হলো chain rule, যা matrix আকারে Jacobian-এর গুণ।

PageRank ও network centrality। Dominant eigenvector। একই গণিত social network-এ influence মাপতে, আর citation network-এ গুরুত্বপূর্ণ পেপার খুঁজতে ব্যবহৃত।

Vector database ও RAG। Embedding + cosine similarity। Pinecone, Weaviate, Qdrant, pgvector — সবার কেন্দ্রে dot product। Approximate nearest neighbour index (HNSW) সেই search-কে O(n) থেকে O(log n)-এ নামায়।

Recommendation। Matrix factorisation — user-item rating matrix-কে দুইটা ছোট matrix-এর গুণফল হিসেবে আনুমানিক করা। Netflix Prize-এর বিজয়ী পদ্ধতির কেন্দ্রে এটাই ছিল।

Signal ও image processing। Convolution, Fourier transform (একটা matrix গুণ হিসেবে দেখা যায়), JPEG-এর DCT — সবই linear transform।

Computer vision। Camera calibration, homography, pose estimation — প্রতিটা matrix সমীকরণ।

PCA ও dimensionality reduction। Covariance matrix-এর eigenvector গুলোই principal component। ৭৬৮-মাত্রার embedding কে ২ মাত্রায় নামিয়ে plot করা — সেটাও এটাই।

Numerical simulation। Finite element method, fluid dynamics, circuit simulation (SPICE) — সবই বিশাল sparse linear system solve করা।

Cryptography। Lattice-ভিত্তিক post-quantum cryptography (Kyber, Dilithium) সরাসরি linear algebra-র উপর দাঁড়ানো।

যে ভুলগুলো সবাই করে

“Matrix গুণ commutative — শুধু ক্রম লেখার ব্যাপার।”

AB ≠ BA — প্রায় কখনোই সমান নয়।

কারণটা গভীর: matrix গুণ হলো function composition, আর f∘g ≠ g∘f। মোজা তারপর জুতো পরা, আর জুতো তারপর মোজা — একই নয়।

R = rotation(90)
T = translation(5, 0)
apply(matmul(T, R), 1, 0)    # (5.0, 1.0)
apply(matmul(R, T), 1, 0)    # (0.0, 6.0)

সম্পূর্ণ ভিন্ন বিন্দু।

3D graphics-এ transformation-এর ক্রম ভুল হওয়াটা সবচেয়ে সাধারণ bug। আর মনে রাখুন M = T·R·S লিখলে S সবার আগে প্রয়োগ হয় — ডান থেকে বামে।

কিছু বিশেষ ক্ষেত্রে commute করে: identity-র সাথে, নিজের power-এর সাথে, আর diagonal matrix-দের মধ্যে। কিন্তু এগুলো ব্যতিক্রম।

আর inverse-এর ক্রমও উল্টো: (AB)⁻¹ = B⁻¹A⁻¹।

“Linear algebra শুধু machine learning-এর জন্য।”

ML সবচেয়ে দৃশ্যমান প্রয়োগ, কিন্তু কালানুক্রমে সবচেয়ে নতুন।

Linear algebra ML-এর অনেক আগে থেকে চলছে:

ক্ষেত্র	কবে থেকে
Graphics	১৯৬০-এর দশক
Numerical simulation	১৯৫০-এর দশক
Signal processing	১৯৪০-এর দশক
Control theory	১৯৫০-এর দশক
Google PageRank	১৯৯৮
Deep learning-এর উত্থান	২০১২

আর আজকের একজন backend engineer-ও এর মুখোমুখি হন: vector database, geospatial query, A/B test-এর পরিসংখ্যান, recommendation, বা শুধু একটা image thumbnail বানানো।

GPU-ই সবচেয়ে বড় প্রমাণ: সেটা graphics-এর জন্য বানানো হয়েছিল, ML-এর জন্য নয়। ML পরে এসে সেই hardware-টা দখল করেছে — কারণ দুটোরই মূল operation একই।

“Determinant শুধু একটা সংখ্যা যেটা হিসাব করতে হয়।”

Determinant একটা প্রশ্নের উত্তর: “এই রূপান্তর কি তথ্য হারায়?”

`det`	জ্যামিতি	Function-এর ভাষায়
`≠ 0`	আয়তন টিকে আছে	injective, invertible
`= 0`	মাত্রা ধসে পড়েছে	injective নয়, inverse নেই
`< 0`	orientation উল্টেছে	invertible, কিন্তু mirror

Functions-এর লেসনের [[injective]] ধারণাটা এখানে হুবহু ফিরে এসেছে — শুধু জ্যামিতিক পোশাকে।

আর হিসাব করার পদ্ধতিটাও গুরুত্বপূর্ণ। Cofactor expansion O(n!) — n = 15-এই অসম্ভব। LU decomposition দিয়ে O(n³)।

বাস্তব numerical কোডে determinant প্রায় হিসাবই করা হয় না, কারণ float-এ সেটা অনির্ভরযোগ্য। তার বদলে condition number বা SVD-র singular value দেখা হয় — সেগুলো বলে matrix-টা কতটা “কাছাকাছি singular”, যা একটা হ্যাঁ/না উত্তরের চেয়ে অনেক বেশি কাজের।

“Eigenvector একটা বিমূর্ত ধারণা, বাস্তবে কাজে লাগে না।”

Eigenvector উত্তর দেয় একটা খুব ব্যবহারিক প্রশ্নের: একটা প্রক্রিয়া বারবার চালালে শেষে কী হয়?

প্রশ্ন	Eigenvector-এর উত্তর
Random surfer দীর্ঘকাল পরে কোথায়?	PageRank
ডেটার সবচেয়ে বেশি তথ্যবহ দিক কোনটা?	PCA-র principal component
একটা সেতু কোন কম্পাঙ্কে দুলবে?	vibration mode
একটা Markov chain কোথায় স্থিতিশীল হয়?	stationary distribution
একটা graph কয়টা cluster-এ ভাগ হয়?	spectral clustering
একটা control system কি স্থিতিশীল?	eigenvalue-র চিহ্ন

Google-এর পুরো ব্যবসাটা শুরু হয়েছিল একটা eigenvector হিসাব করে। Spotify-র recommendation, Netflix-এর matrix factorisation, প্রতিটা recommendation engine-এর ভেতরে eigen-decomposition বা তার আত্মীয় SVD আছে।

আর quantum computing-এ একটা measurement-এর সম্ভাব্য ফলাফল আক্ষরিকভাবে একটা operator-এর eigenvalue।

বুঝেছেন কি না দেখুন

একটা neural network-এ যদি সব activation function বাদ দেওয়া হয় (শুধু matrix গুণ থাকে), তাহলে ১০০ layer-এর network কতটা শক্তিশালী হবে?

যুক্তি

ঠিক একটা layer-এর সমান। গভীরতা সম্পূর্ণ অর্থহীন হয়ে যাবে।

h₁ = W₁x
h₂ = W₂W₁x
h₃ = W₃W₂W₁x
⋮
h₁₀₀ = W₁₀₀ ⋯ W₂W₁ x

কিন্তু W₁₀₀ ⋯ W₂W₁ নিজেই একটা matrix। ধরুন W = W₁₀₀⋯W₁:

$\mathbf{h}_{100} = W\mathbf{x}$

একটামাত্র matrix গুণ।

কেন: linear map-দের composition আবার linear। এটা [[function]]-এর লেসনের composition ধর্মের সরাসরি পরিণতি — একটা শ্রেণির function compose করলে সেই শ্রেণিতেই থাকে।

পরিণতি: activation ছাড়া network শুধু linear function শিখতে পারে। XOR-ও শিখতে পারবে না, কারণ XOR linearly separable নয় — এটাই ১৯৬৯-এ Minsky ও Papert-এর perceptron সমালোচনা, যা AI winter-এর একটা কারণ হয়েছিল।

Non-linearity কী যোগ করে:

h = ReLU(Wx + b) = max(0, Wx + b)

ReLU সরল — একটা comparison। কিন্তু সেটাই composition ভেঙে দেয়, আর universal approximation theorem অনুযায়ী যথেষ্ট প্রশস্ত একটা network তখন যেকোনো continuous function approximate করতে পারে।

তবে একটা সূক্ষ্মতা: গভীর network তাত্ত্বিকভাবে অগভীর network-এর চেয়ে বেশি শক্তিশালী নয় (universal approximation এক layer-এই কাজ করে)। গভীরতার সুবিধা হলো দক্ষতা — একই function অনেক কম parameter-এ প্রকাশ করা যায়।

Level 13-এ আমরা AI/ML foundation-এ এটা বিস্তারিত দেখব।

এই দুইটা matrix-এর determinant বের করুন এবং বলুন কোনটা invertible:

$A = \begin{bmatrix} 3 & 1 \\ 2 & 4 \end{bmatrix}, \qquad B = \begin{bmatrix} 2 & 6 \\ 1 & 3 \end{bmatrix}$

প্রয়োগ

$\det A = 3(4) - 1(2) = 12 - 2 = 10$ $\det B = 2(3) - 6(1) = 6 - 6 = 0$

A invertible (det = 10 ≠ 0), B নয়।

B-তে কী ঘটেছে: দ্বিতীয় সারি [1, 3] প্রথম সারি [2, 6]-এর ঠিক অর্ধেক। দুইটা সারি linearly dependent — দ্বিতীয়টা কোনো নতুন তথ্য দিচ্ছে না।

জ্যামিতিকভাবে: B পুরো 2D সমতলকে একটা রেখায় চেপে দেয়। কলাম দুইটা দেখুন — [2,1] আর [6,3], আর [6,3] = 3·[2,1]। দুটোই একই দিকে, তাই output সবসময় সেই একটা রেখায়।

Injectivity হারিয়েছে: অসংখ্য ভিন্ন input একই output দেয়।

B·[3, -1]ᵀ = [2(3)+6(-1), 1(3)+3(-1)]ᵀ = [0, 0]ᵀ
B·[0,  0]ᵀ = [0, 0]ᵀ

দুইটা ভিন্ন input, একই output — [[injective]] নয়, তাই inverse নেই।

{x : Bx = 0} কে বলে null space। B-এর null space একটা রেখা ([3,-1]-এর গুণিতক), তাই rank(B) = 1।

A-এর inverse:

$A^{-1} = \frac{1}{\det A}\begin{bmatrix} 4 & -1 \\ -2 & 3 \end{bmatrix} = \begin{bmatrix} 0.4 & -0.1 \\ -0.2 & 0.3 \end{bmatrix}$

যাচাই: A · A⁻¹ করলে identity আসবে।

প্রকৌশলগত সতর্কতা: float গণনায় det B ঠিক 0 না হয়ে 1e-16 হতে পারে। তখন inverse “কাজ করবে” কিন্তু ফলাফল আবর্জনা। তাই det নয়, condition number দেখুন — আর numpy.linalg.solve(A, b) ব্যবহার করুন, inv(A) @ b নয়।

আপনি একটা semantic search বানাচ্ছেন ১০ লক্ষ document-এর উপর, প্রতিটা ৭৬৮-মাত্রার embedding। প্রতিটা query-তে সব document-এর সাথে cosine similarity মাপলে কী সমস্যা, আর কী করবেন?

ডিজাইন

Brute force-এর খরচ:

প্রতিটা similarity = ৭৬৮টা গুণ + ৭৬৮টা যোগ ≈ ১৫৩৬ FLOP।

10⁶ document × 1536 FLOP = 1.5 GFLOP প্রতি query

একটা CPU core ~১০ GFLOP/s দিলে প্রতি query-তে ~১৫০ ms — আর সেটা শুধু arithmetic, memory bandwidth ধরলে আরো খারাপ।

Memory: 10⁶ × 768 × 4 byte = 3 GB (float32)। প্রতিটা query-তে পুরো ৩ GB পড়তে হবে — সাধারণ RAM bandwidth (~২০ GB/s) ধরলে সেটাই ১৫০ ms।

১০০ QPS চাইলে অসম্ভব।

সমাধান, কার্যকারিতার ক্রমে:

১. Normalise করে রাখুন (সবচেয়ে সহজ লাভ)। Vector গুলো আগেই unit length করে রাখলে cosine = শুধু dot product। বর্গমূল আর ভাগ বাদ — প্রায় ৩০% সাশ্রয়।

২. Approximate Nearest Neighbour index। এটাই আসল সমাধান।

Index	ধরন	Recall	গতি
HNSW	graph-ভিত্তিক	~০.৯৫+	`O(log n)`
IVF	clustering	~০.৯০	cluster-এর অংশ স্ক্যান
LSH	hashing	কম	দ্রুত

HNSW একটা multi-layer navigable small-world graph — graph theory-র লেসনের small-world ধারণাটাই এখানে। 10⁶ document-এ query নেমে আসে ~১ ms-এ।

৩. Quantisation। float32 → int8 করলে memory ৪ গুণ কমে (3 GB → 750 MB), আর SIMD-তে বেশি মান একসাথে প্রক্রিয়া হয়। Recall সামান্য কমে।

Product quantisation আরো এগিয়ে — ৩২ গুণ পর্যন্ত compression।

৪. Dimensionality reduction। PCA দিয়ে ৭৬৮ → ২৫৬ মাত্রা। তিন গুণ কম কাজ, আর প্রায়ই recall প্রায় অপরিবর্তিত — কারণ বেশিরভাগ variance কম মাত্রাতেই ধরা পড়ে।

৫. Two-stage retrieval। সস্তা index দিয়ে ১০০০টা প্রার্থী আনুন, তারপর সেই ১০০০-এর উপর নিখুঁত (বা আরো ব্যয়বহুল cross-encoder) scoring। Production RAG system-এ এটাই প্রামাণ্য নকশা।

সুপারিশ: HNSW + normalised vector + দুই-স্তরের retrieval। pgvector, Qdrant, Weaviate — সবাই এটাই দেয়।

Trade-off যা স্পষ্ট করে রাখতে হবে: ANN মানে approximate — মাঝে মাঝে সঠিক শীর্ষ ফলাফল মিস হবে। Recall বনাম latency-র সেই বিনিময়টা measure করে ঠিক করতে হয়, অনুমান করে নয়।

Level 8-এ index structure আর Level 11-এ SIMD/quantisation বিস্তারিত দেখব।

ijk আর ikj loop order-এ FLOP সংখ্যা হুবহু একই, তবু ikj তিন গুণ দ্রুত। ব্যাখ্যা করুন, আর বলুন jki order কেমন হবে।

প্রয়োগ

কারণ — memory access pattern, arithmetic নয়।

Row-major layout-এ A[i][j] আর A[i][j+1] পাশাপাশি; কিন্তু A[i][j] আর A[i+1][j]-এর মধ্যে N × 8 byte দূরত্ব।

ijk — ভেতরের loop k:

for (k) s += A[i][k] * B[k][j];

A[i][k] — k বাড়ছে, সারি ধরে → sequential, hit
B[k][j] — k বাড়ছে, কলাম ধরে লাফাচ্ছে → প্রতিবার নতুন cache line, miss

N = 512, double হলে প্রতি লাফ ৪০৯৬ byte। পুরো B matrix ২ MB — L2 cache-এ আঁটে না, তাই প্রায় প্রতিবারই miss।

ikj — ভেতরের loop j:

for (j) C[i][j] += a * B[k][j];

B[k][j] — j বাড়ছে, সারি ধরে → sequential
C[i][j] — j বাড়ছে, সারি ধরে → sequential
A[i][k] — ভেতরের loop-এ স্থির, register-এ রাখা যায়

একটা ৬৪-byte cache line-এ ৮টা double, তাই ৮টার মধ্যে ৭টা hit। উপরন্তু hardware prefetcher sequential pattern চিনে আগেই পরের line এনে রাখে।

jki — সবচেয়ে খারাপ:

for (j) for (k) for (i) C[i][j] += A[i][k] * B[k][j];

C[i][j] — i বাড়ছে, কলাম ধরে → miss
A[i][k] — i বাড়ছে, কলাম ধরে → miss
B[k][j] — ভেতরের loop-এ স্থির → ঠিক আছে

দুইটা array-ই কলাম ধরে — ijk-এর চেয়েও খারাপ।

ছয়টা order-এর আনুমানিক ক্রম (row-major, বড় N):

Order	ভেতরের loop-এ sequential	আপেক্ষিক গতি
`ikj`, `kij`	২টা	দ্রুততম
`ijk`, `jik`	১টা	মাঝারি
`jki`, `kji`	০টা	ধীরতম

Column-major ভাষায় (Fortran, MATLAB) ঠিক উল্টো — তাই “সেরা loop order” ভাষা-নির্ভর, সর্বজনীন নয়।

আসল সমাধান — tiling: পুরো matrix cache-এ আঁটে না, কিন্তু একটা 32×32 block আঁটে। Block ধরে কাজ করলে প্রতিটা block একবার এনে বহুবার ব্যবহার করা যায়।

BLAS library (OpenBLAS, MKL) tiling + SIMD + prefetch + multi- thread মিলিয়ে naive কোডের চেয়ে ৫০–১০০ গুণ দ্রুত। তাই নিজে matrix multiply লিখবেন না — শেখার জন্য ছাড়া।

Level 3-এ cache-এর গঠন, Level 11-এ tiling ও SIMD দেখব।

Ax = b -এর “কোনো সমাধান নেই”, “একটা সমাধান”, আর “অসীম সমাধান” — তিনটা ক্ষেত্র জ্যামিতিকভাবে কী বোঝায়?

যুক্তি

Ax = b প্রশ্নটা আসলে: b কি A-এর column space-এ আছে?

কারণ Ax মানে A-এর কলামগুলোর একটা linear combination:

$A\mathbf{x} = x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \cdots + x_n\mathbf{a}_n$

ক্ষেত্র ১ — ঠিক একটা সমাধান।

A full rank (det ≠ 0)। কলামগুলো পুরো space span করে, আর কোনো redundancy নেই। b যেখানেই থাকুক, ঠিক একভাবে পৌঁছানো যায়।

2x + y = 5
 x − y = 1     →  x = 2, y = 1

দুইটা রেখা ঠিক একটা বিন্দুতে ছেদ করে।

ক্ষেত্র ২ — অসীম সমাধান।

rank(A) < n, কিন্তু b column space-এ আছে।

2x + 4y = 10
 x + 2y = 5      →  একই সমীকরণ

দুইটা রেখা একই রেখা — প্রতিটা বিন্দুই সমাধান।

সাধারণ সমাধান = একটা নির্দিষ্ট সমাধান + null space:

$\mathbf{x} = \mathbf{x}_p + \mathbf{x}_{\text{null}}$

ক্ষেত্র ৩ — কোনো সমাধান নেই।

rank(A) < n এবং b column space-এর বাইরে।

2x + 4y = 10
 x + 2y = 6      →  বিরোধী

দুইটা সমান্তরাল রেখা — কখনো ছেদ করে না।

তৃতীয় ক্ষেত্রটাই বাস্তবে সবচেয়ে সাধারণ

বাস্তব ডেটায় সমীকরণ প্রায় সবসময় সমীকরণের চেয়ে বেশি (overdetermined), আর measurement noise-এর কারণে নিখুঁত সমাধান থাকে না।

তখন আমরা প্রশ্নটা বদলাই: নিখুঁত সমাধানের বদলে সবচেয়ে কাছের সমাধান চাই —

$\min_{\mathbf{x}} \|A\mathbf{x} - \mathbf{b}\|^2$

এটাই least squares, আর এর সমাধান normal equation:

$A^TA\mathbf{x} = A^T\mathbf{b}$

জ্যামিতিকভাবে: b কে column space-এ projection করা।

আর এটাই linear regression। প্রতিটা linear model fit করা মানে এই সমীকরণ solve করা। Curve fitting, sensor fusion, GPS positioning, camera calibration — সবই least squares।

বাস্তবে normal equation সরাসরি solve করা হয় না (numerically unstable) — QR বা SVD decomposition ব্যবহার হয়।

সংক্ষেপে:

`rank(A)`	`b` column space-এ?	সমাধান
`= n`	সবসময়	ঠিক একটা
`< n`	হ্যাঁ	অসীম
`< n`	না	নেই → least squares

এরপর কী

Linear algebra দিয়ে আমরা রূপান্তরের ভাষা পেলাম — আর দেখলাম functions-এর লেসনের composition, injectivity আর invertibility কীভাবে সংখ্যার জগতে ফিরে আসে।

Level 0-এর শেষ লেসনটা আসছে: asymptotic notation।

এতক্ষণ আমরা শিখেছি কীভাবে জিনিস প্রকাশ করতে হয় আর প্রমাণ করতে হয়। শেষ প্রশ্নটা হলো: দুইটা সঠিক সমাধানের মধ্যে কোনটা ভালো, আর “ভালো” মানে ঠিক কী?

O, Θ, Ω আনুষ্ঠানিকভাবে, Master Theorem, amortised analysis — আর সবচেয়ে গুরুত্বপূর্ণ: কখন এই বিমূর্তকরণটা মিথ্যা বলে। আজকের experiment-এ আমরা তার একটা ঝলক দেখেছি — একই FLOP, তিন গুণ সময়ের পার্থক্য।

Linear Algebra — রূপান্তরের ভাষা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Vector — তিনটা ভিন্ন পাঠ

Dot product — একটামাত্র সংখ্যা, বিশাল কাজ

Cosine similarity — search আর recommendation-এর ইঞ্জিন

Matrix = function

Matrix গুণ = composition

Determinant — তথ্য হারাচ্ছে কি না

Eigenvector — যে দিকগুলো ঘোরে না

ভেতরে কী ঘটছে

PageRank = dominant eigenvector

Neural network — কেন non-linearity ছাড়া চলে না

Homogeneous coordinates — translation-কে matrix বানানো

Memory layout — যেখানে গণিত hardware-এ ধাক্কা খায়

উদাহরণ

Embedding আর similarity — একটা সম্পূর্ণ উদাহরণ

Determinant শূন্য — একটা বাস্তব সমস্যা

নিজে চালিয়ে দেখুন

Cosine similarity নিজে চালিয়ে দেখুন

Loop order বদলে ৩ গুণ গতি — একই FLOP-এ

নিজে বানান

Linear Algebra শূন্য থেকে — numpy ছাড়া

বাস্তব সিস্টেমে

Linear algebra যেখানে যেখানে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Vector — তিনটা ভিন্ন পাঠ

Dot product — একটামাত্র সংখ্যা, বিশাল কাজ

Cosine similarity — search আর recommendation-এর ইঞ্জিন

Matrix = function

Matrix গুণ = composition

Determinant — তথ্য হারাচ্ছে কি না

Eigenvector — যে দিকগুলো ঘোরে না

⚙ভেতরে কী ঘটছেUnder the hood

PageRank = dominant eigenvector

Neural network — কেন non-linearity ছাড়া চলে না

Homogeneous coordinates — translation-কে matrix বানানো

Memory layout — যেখানে গণিত hardware-এ ধাক্কা খায়

▶উদাহরণExample

Embedding আর similarity — একটা সম্পূর্ণ উদাহরণ

Determinant শূন্য — একটা বাস্তব সমস্যা

⌘নিজে চালিয়ে দেখুনExperiment

Cosine similarity নিজে চালিয়ে দেখুন

Loop order বদলে ৩ গুণ গতি — একই FLOP-এ

⚒নিজে বানানBuild it yourself

Linear Algebra শূন্য থেকে — numpy ছাড়া

◉বাস্তব সিস্টেমেReal-world usage

Linear algebra যেখানে যেখানে

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী