From-scratch Python implementations of Gaussian elimination, SVD decomposition, and matrix diagonalization — with a narrated Manim video and performance analysis.
This project covers three core areas of numerical linear algebra, implemented from scratch in Python without the use of numpy.linalg, scipy.linalg, or sympy solver functions. NumPy and SciPy are used only for result verification.
| Part | Topic | Status |
|---|---|---|
| 1 | Gaussian elimination, determinant, inverse, rank/basis | Mandatory |
| 2 | Singular Value Decomposition (SVD), diagonalization, Manim video with narration | Mandatory |
| 3 | Iterative solvers, benchmarks, stability analysis | Bonus |
matdecomp/
├── README.md
├── CONTRIBUTING.md
├── LICENSE
├── requirements.txt
├── manim.cfg # Custom Manim theme
├── part1/
│ ├── gaussian.py # gaussian_eliminate, back_substitution
│ ├── determinant.py # determinant
│ ├── inverse.py # inverse (Gauss-Jordan)
│ ├── rank_basis.py # rank_and_basis
│ └── part1_demo.ipynb # Walkthrough notebook
├── part2/
│ ├── decomposition.py # svd_decompose
│ ├── diagonalization.py # diagonalize (A = PDP⁻¹)
│ ├── manim/
│ │ ├── img/ # Static image assets
│ │ ├── svg/ # Vector assets
│ │ ├── scene_intro.py # Intro scene logic
│ │ ├── scene_svd.py # Singular Value Decomposition logic
│ │ ├── scene_compare.py # Comparison logic
│ │ ├── scene_app.py # Application demonstration logic
│ │ ├── theme.py # Shared Manim color/font config
│ │ ├── manim.cfg # Local Manim config
│ │ └── demo_video.mp4 # Exported video
│ └── manim-prod-assets/
│ ├── assets_attribution_list.md
│ ├── narration_script.md
│ ├── svd-animation-refs.md
│ └── svd-animation-rules.md
├── part3/ # Bonus — only present if activated
│ ├── solvers.py # Gauss-Seidel iterative solver
│ ├── benchmark.py # Benchmark harness
│ ├── results.csv # Benchmark results
│ └── analysis.ipynb # Performance analysis notebook
└── report/
├── report.tex # LaTeX source
├── report.pdf # Compiled report
├── reportDoCS2025.cls # Custom LaTeX class for report styling and layout
├── latexmkrc # Build configuration file for automated LaTeX compilation
├── logos
└── chapters/
├── chapter_01.tex
├── chapter_02.tex
├── chapter_03.tex
├── conclusion.tex
└── biblio.tex
- Python 3.10 or higher
- Manim Community v0.20.1
- WSL2 (Ubuntu) or Windows — see note below
pip install -r requirements.txtThis project is developed across WSL2 (Ubuntu) and Windows. Line endings are normalized via .gitattributes. If you are on Windows, run the following once after cloning:
git config --global core.autocrlf falseAll file paths in the codebase use pathlib.Path — no hardcoded OS separators.
manim --version
# Expected: Manim Community v0.20.1If Manim installation fails on Windows, refer to the official Windows installation guide. WSL2 users generally have fewer install issues.
Implementations in part1/:
| Function | Description |
|---|---|
gaussian_eliminate(A, b) |
Gaussian elimination with partial pivoting. Returns reduced matrix, solution x, swap count s. |
back_substitution(U, c) |
Backward substitution for upper-triangular systems. |
determinant(A) |
Computes det(A) = (−1)ˢ × ∏ uᵢᵢ via elimination. |
inverse(A) |
Finds A⁻¹ via Gauss-Jordan on [A|I]. |
rank_and_basis(A) |
Returns rank, column space basis, row space basis, and null space basis from RREF. |
verify_solution(A, x, b) |
Computes residual ‖Ax̂−b‖₂/‖b‖₂ and compares against NumPy. |
Each function has at least 5 test cases including edge cases. See part1/part1_demo.ipynb for a full walkthrough.
Python implementation in part2/decomposition.py and part2/diagonalization.py:
svd_decompose(A)— Computes the Singular Value Decomposition A = UΣV^T.diagonalize(A)— Returns P, D, P_inv satisfying A = PDP⁻¹.
Manim video (part2/manim/demo_video.mp4):
The video is a narrated educational animation in the style of a math explainer, with a custom light theme distinct from 3Blue1Brown defaults.
| Scene | Content |
|---|---|
| 1 | Diagonalization Introduction |
| 2 | Singular Value Decomposition Overview |
| 3 | Connections between diagonalization and SVD |
| 4 | Application — data compression, image processing, PCA and LSA using SVD |
Narration uses Google's Text-to-Speech service. Narration script at part2/manim-prod-assets/narration_script.md.
Present only if activated during Sprint 3 planning. Compares Gaussian elimination, SVD solver, and Gauss-Seidel across matrix sizes n ∈ {50, 100, 200, 500, 1000}. Includes log-log plots and stability analysis on Hilbert matrices vs random SPD matrices. See part3/analysis.ipynb.
# Part 1 demo
jupyter notebook part1/part1_demo.ipynb
# Part 3 analysis (if present)
jupyter notebook part3/analysis.ipynbAll notebooks run top-to-bottom without manual intervention.
cd part2/manim
manim -q[quality: l-low, m-medium, h-high] [file name] [scene name] --disable_cachingThe -qh flag renders at 1080p. Output goes to media/videos/. The pre-rendered export with narration is at part2/manim/demo_video.mp4.
| Member | Role | Responsibilities |
|---|---|---|
| Trần Văn Tấn Khôi | Product Owner + Repo Owner | Backlog, GitHub Projects, verify_solution |
| Lê Thành Đạt | Scrum Master | Sprint ceremonies, retros, report Prism → Git commits |
| Cao Việt Cường | Developer A | gaussian_eliminate, back_substitution, rank_and_basis, benchmark harness |
| Nguyễn Phú Đạt | Developer B | determinant, inverse, part1_demo.ipynb |
| Lê Thành Đạt | Developer C | SVD decomposition skeleton and full implementation |
| Mai Phan Nhật Hoàng | Developer D | Diagonalization (stub and complete), report sections |
| Trần Văn Tấn Khôi | Developer E | All Manim scenes, narration script, AI voiceover and sync, video export |
This project uses a structured GitHub workflow. Please read before pushing anything.
feat/short-description # new implementation or feature
fix/short-description # bug fix
docs/short-description # report, notebook, or README changes
feat: add partial pivoting to gaussian_eliminate
fix: handle singular matrix edge case in determinant
test: add 5 edge cases for inverse()
docs: draft Part 1 theory section
One logical change per commit. Do not commit commented-out code or debugging print statements.
- Open a PR against
dev, notmain - Title must reference the issue:
feat: gaussian_eliminate (#3) - At least one reviewer required — do not merge your own PR
- All acceptance criteria on the linked issue must be checked before requesting review
mainis protected and only receives merges fromdevat sprint close
Every story has a corresponding GitHub Issue. Before starting work:
- Assign the issue to yourself
- Move the card to In Progress on the project board
- Create a branch linked to the issue
Đây là đồ án cài đặt bằng Python các kỹ thuật đại số tuyến tính số, bao gồm phép khử Gauss, phân rã giá trị suy biến (SVD), và chéo hóa ma trận, kèm video Manim có thuyết minh và phân tích hiệu năng.
Phần 1 — Phép Khử Gauss và Ứng Dụng
Cài đặt: gaussian_eliminate (có partial pivoting), back_substitution, determinant, inverse (Gauss-Jordan), rank_and_basis. Không sử dụng numpy.linalg hoặc scipy.linalg trong phần cài đặt — chỉ dùng để kiểm chứng.
Phần 2 — Phân Rã SVD + Video Manim Phân rã giá trị suy biến (SVD) A = UΣV^T. Chéo hóa ma trận A = PDP⁻¹. Video Manim có thuyết minh giải thích trực quan về SVD (≥2 phút, ≥1080p) với theme tùy chỉnh — nền sáng, font IBM Plex Sans, màu teal.
Phần 3 — Phân Tích Hiệu Năng So sánh các phương pháp giải Ax = b: Gauss, SVD, Gauss-Seidel. Thực nghiệm với n ∈ {50, 100, 200, 500, 1000}. Đồ thị log-log, phân tích ma trận Hilbert. Chỉ thực hiện nếu có đủ thời gian sau Phần 1 và 2.
pip install -r requirements.txtYêu cầu Python 3.10 trở lên và Manim Community v0.20.1.
Dự án phát triển trên cả WSL2 (Ubuntu) và Windows. File .gitattributes đã cấu hình thống nhất line ending (LF). Thành viên dùng Windows chạy lệnh sau sau khi clone:
git config --global core.autocrlf falseMỗi story tương ứng một GitHub Issue. Làm việc trên branch riêng, tạo Pull Request vào dev, cần ít nhất 1 người review trước khi merge. Không ai merge PR của chính mình. Xem hướng dẫn đầy đủ ở phần Contributing phía trên.