Part VIII — Glossary (Computational Linear Algebra)

Part VIII-এর চার chapter-এ (8.1–8.4) প্রথম দেখা সব গুরুত্বপূর্ণ term এক টেবিলে — chapter অনুযায়ী সাজানো।

Chapter 8.1 — Floating Point ও Conditioning

English Term	বাংলা	এক লাইনে অর্থ
Floating Point	ফ্লোটিং পয়েন্ট	কম্পিউটারের ভাসমান-দশমিক সংখ্যা-ব্যবস্থা: \(\pm(1.b_1\ldots b_{52})_2 \times 2^e\) — সসীম ঘরে বিশাল range
IEEE 754 Double Precision	ডাবল প্রিসিশন	৬৪-bit standard (Python-এর float): ১ sign + ১১ exponent + ৫২ mantissa bit
Mantissa (Significand)	ম্যান্টিসা	সংখ্যার "অঙ্কগুলো" binary-তে — ৫২ bit, সামনের \(1.\) ফ্রি
Machine Epsilon	মেশিন এপসাইলন	\(\varepsilon_{\text{mach}} = 2^{-52} \approx 2.2\times10^{-16}\) — \(1\)-এর পরের representable সংখ্যার দূরত্ব; ১৬-digit সততা
Rounding Error	রাউন্ডিং এরর	প্রতিটা operation-এ \(\text{fl}(x) = x(1+\delta)\), \(\vert \delta\vert \le \tfrac12\varepsilon_{\text{mach}}\) — কাছের দাগে গোল করার অনিবার্য ভুল
Condition Number	কন্ডিশন নাম্বার	\(\kappa(A) = \sigma_1/\sigma_n \ge 1\) — সমস্যা নিজে কতটা স্পর্শকাতর: input-এর ছোট নাড়া output-এ কত বড় নাড়া আনে
Conditioning	কন্ডিশনিং	সমস্যার অন্তর্নিহিত রোগ — ভালো (well) বনাম খারাপ (ill) conditioned; algorithm বদলে সারে না
Catastrophic Cancellation	ক্যাটাস্ট্রফিক ক্যানসেলেশন	প্রায়-সমান দুই সংখ্যার বিয়োগে সামনের digit কেটে গিয়ে আপেক্ষিক ভুল \(10^{-16}\) থেকে \(\sim1\)-এ লাফ
Stability	স্ট্যাবিলিটি	algorithm-এর সততা — "algorithm-এর দোষ", conditioning-এর ("সমস্যার দোষ") থেকে আলাদা
Backward Stability	ব্যাকওয়ার্ড স্টেবিলিটি	computed উত্তর = একটু-নাড়ানো প্রশ্নের নিখুঁত উত্তর; তখন rel. error \(\lesssim \kappa(A)\varepsilon_{\text{mach}}\)
Overflow / Underflow	ওভারফ্লো / আন্ডারফ্লো	সংখ্যা range-এর বাইরে (\(\infty\)/NaN) বা এত ছোট যে \(0\) হয়ে যায় — softmax-এ \(e^{1000}\), log-এ \(\log 0\)

Chapter 8.2 — Ax=b বাস্তবে

English Term	বাংলা	এক লাইনে অর্থ
Factorization	ফ্যাক্টরাইজেশন	matrix-কে একবার সহজ টুকরোয় ভাঙা ("চাবি বানানো"), তারপর বহু \(b\)-তে সস্তায় reuse
LU Decomposition	এলইউ ডিকম্পোজিশন	\(PA = LU\) — Gaussian elimination-এর ডায়েরি; general square, খরচ \(\sim\frac23 n^3\)
Cholesky Decomposition	কোলেস্কি ডিকম্পোজিশন	\(A = LL^T\) — শুধু SPD matrix-এ, LU-এর অর্ধেক খরচ (\(\sim\frac13 n^3\)); ভেঙে পড়াই দ্রুততম SPD-পরীক্ষা
QR Decomposition	কিউআর ডিকম্পোজিশন	\(A = QR\) (\(Q\) orthonormal, \(R\) upper triangular) — least squares-এর নিরাপদ পথ, খরচ \(\sim 2mn^2\)
Permutation Matrix	পারমিউটেশন ম্যাট্রিক্স	\(P\) — শুধু row অদল-বদল করে; pivoting-এর হিসাব রাখে (\(PA = LU\)-তে)
Partial Pivoting	পারশিয়াল পিভটিং	প্রতি ধাপে column-এর সবচেয়ে বড় সংখ্যাকে pivot বানানো — stability, আর কখনো অস্তিত্বের জন্যও লাগে
Forward Substitution	ফরওয়ার্ড সাবস্টিটিউশন	Lower triangular \(Lc = b\) ওপর থেকে নিচে সমাধান — খরচ মাত্র \(\sim n^2\)
Back Substitution	ব্যাক সাবস্টিটিউশন	Upper triangular \(Ux = c\) নিচ থেকে ওপরে সমাধান — খরচ মাত্র \(\sim n^2\)
Complexity	কমপ্লেক্সিটি	বৃদ্ধির হার, ধ্রুবক নয়: \(O(n^3)\) মানে \(n\) দ্বিগুণ হলে খরচ আট গুণ
FLOP	ফ্লপ	floating point operation-এর গোনা — algorithm-এর খরচের একক
Sparse Matrix	স্পার্স ম্যাট্রিক্স	বেশিরভাগ ঘর শূন্য — খরচ nonzero সংখ্যা ও কাঠামোর ওপর নির্ভর, \(n\)-এর নয়
Fill-in	ফিল-ইন	factorization-এ আগের শূন্য ঘরগুলো nonzero হয়ে ওঠা — ভালো ordering দিয়ে কমানো যায়
Iterative Method (CG)	ইটারেটিভ মেথড	\(A\) factor না করে বারবার matrix-vector গুণে সমাধান; SPD-তে Conjugate Gradient — বিশাল sparse-এ একমাত্র উপায়

Chapter 8.3 — Eigenvalue Algorithms

English Term	বাংলা	এক লাইনে অর্থ
Power Method	পাওয়ার মেথড	\(x_{k+1} = Ax_k/\|Ax_k\|\) — বারবার গুণ + normalize → dominant eigenvector (PageRank-এর প্রাণ)
Dominant Eigenvalue	ডমিন্যান্ট আইগেনভ্যালু	সবচেয়ে বড় মানের \(\lambda_1\) (\(\vert \lambda_1\vert > \vert \lambda_2\vert\)) — power method যেটার eigenvector ধরে
Convergence Rate	কনভার্জেন্স রেট	power method-এর গতি \(\propto \vert \lambda_2/\lambda_1\vert\) — eigenvalue-দের gap বড় = দ্রুত, ছোট = স্থবির
Rayleigh Quotient	রেইলি কোশেন্ট	\(R(x) = \frac{x^TAx}{x^Tx}\) — eigenvalue-র সেরা অনুমান; symmetric-এ ভুল \(O(\epsilon^2)\), দ্বিগুণ নির্ভুল
Inverse Iteration	ইনভার্স ইটারেশন	\(A^{-1}\)-এ power method → সবচেয়ে ছোট eigenvalue (matrix উল্টাও — factor করে, invert নয়)
Shifted Inverse Iteration	শিফটেড ইনভার্স ইটারেশন	\((A-\mu I)^{-1}\)-এ power method → \(\mu\)-এর নিকটতম eigenvalue; ভালো shift = কৃত্রিম বিশাল gap = টার্বো
Shift	শিফট	\(\mu\) — target eigenvalue-র কাছাকাছি আন্দাজ; \(\lambda_i - \mu\) ছোট করে convergence দ্রুত করে
QR Algorithm	কিউআর অ্যালগরিদম	\(A_k = Q_kR_k \to A_{k+1} = R_kQ_k\) বারবার — matrix triangular হয়, diagonal-এ সব eigenvalue
Similarity Transformation	সিমিলারিটি ট্রান্সফরমেশন	\(A_{k+1} = Q_k^{-1}A_kQ_k\) — basis ঘোরায়, eigenvalue অপরিবর্তিত রাখে (QR algorithm-এর ভিত্তি)
Wilkinson's Shock	উইলকিনসনের ধাক্কা	polynomial-এর মূল coefficient-এর প্রতি ভয়ংকর সংবেদনশীল — তাই \(\det(A-\lambda I)=0\)-এর মূল খোঁজা নিষিদ্ধ
Abel–Ruffini Theorem	আবেল–রুফিনি থিওরেম	degree \(\ge 5\) polynomial-এর মূল বের করার সাধারণ সূত্র নেই — তাই eigenvalue algorithm অবশ্যই iterative
Real Schur Form	রিয়েল শুর ফর্ম	non-symmetric matrix-এ QR-এর ফল: quasi-triangular — \(2\times2\) block-এ complex conjugate eigenvalue জোড়া

Chapter 8.4 — Randomized Methods

English Term	বাংলা	এক লাইনে অর্থ
Sketching	স্কেচিং	বিশাল matrix-কে random matrix দিয়ে গুণ করে ছোট করা, তবু জ্যামিতি বজায় (exit poll-এর মতো নমুনা)
Random Projection	র‍্যান্ডম প্রজেকশন	\(Y = A\Omega\) — \(A\)-কে \(k\)টা "random প্রশ্ন" করে column space-এর নমুনা তোলা
Randomized SVD	র‍্যান্ডমাইজড এসভিডি	চার ধাপ (Halko–Martinsson–Tropp): sketch → orthonormalize (\(QR\)) → compress (\(B=Q^TA\)) → tiny SVD
Low-Rank Structure	লো-র‍্যাঙ্ক কাঠামো	matrix-এর আসল তথ্য কয়েকটা দিকে জমা, বাকিটা noise — randomized SVD-র সাফল্যের পূর্বশর্ত
Johnson–Lindenstrauss Lemma	জনসন–লিন্ডেনস্ট্রাস লেমা	random projection দূরত্ব \((1\pm\epsilon)\)-এ রক্ষা করে; target মাত্রা \(k = O(\epsilon^{-2}\log N)\) — \(n\)-নিরপেক্ষ
Oversampling	ওভারস্যাম্পলিং	\(k\)-এর বদলে \(k+p\) column (\(p\approx5\)–\(10\)) — প্রায়-বিনামূল্যের বীমা, নির্ভুলতা নাটকীয়ভাবে বাড়ায়
Power Iteration (\(q\))	পাওয়ার ইটারেশন	\(Y = (AA^T)^qA\Omega\) — \(\sigma_i \to \sigma_i^{2q+1}\), singular value ধীরে কমলে sketch তীক্ষ্ণ করে
Eckart–Young (bound)	একার্ট–ইয়াং	সেরা rank-\(k\) approximation-এর ভুল \(\sigma_{k+1}\) — randomized SVD এর খুব কাছে (near-optimal)
Singular Value Decay	সিঙ্গুলার ভ্যালু ডিকে	singular value কত দ্রুত পড়ে — দ্রুত পতন = randomized SVD-র স্বর্গ, ধীর পতন = সাবধান
Concentration of Measure	কনসেনট্রেশন অফ মেজার	high dimension-এ random বস্তু প্রায় নিশ্চিতভাবে "সাধারণ" আচরণ করে — কেন randomness এখানে বন্ধু
Random Features	র‍্যান্ডম ফিচারস	বিশাল kernel matrix না বানিয়ে random projection দিয়ে তার প্রায়-প্রতিরূপ (SVM, GP বড় data-তে)
Streaming / One-pass	স্ট্রিমিং	data একবারই দেখা যায় এমন ক্ষেত্রে sketching দিয়ে চলতি-চলতি summary — full matrix memory-তে না রেখেই