(tiếp theo phần 1 : 10 và 25 … (phần 1 : Monte Carlo và Simplex method))
- 1950: Krylov subspace iteration methods của Magnus Hestenes et.al
Iterative method (phương pháp lặp) là một trong những công cụ lợi hại nhất trong algorithm design, tôi thích tư tưởng của nó vì nó rất intuitive (cực kỳ đơn giản, xuất phát từ một số dự đoán ngẫu nhiên, xây dựng các lời giải tiếp theo dựa trên những lời giải hiện tại cho tới khi nào đủ tốt hoặc không còn đủ thời gian thì stop. Magnus Hestenes và các đồng nghiệp đã phát minh ra một trong những phương pháp lặp hay nhất trong lịch sử nghành này để giải một trong những bài toán kinh điển nhất trong đại số tuyến tính Krylov subspace (tôi không nhớ hoặc không biết dịch tiếng Việt ra sao). Chân thành mà nói, tôi không đọc original paper mà chỉ đọc những đoạn viết review về thuật toán này. Tư tưởng rất đơn giản mà tuyệt vời, sử dụng gradient method nổi tiếng để xấp chỉ chuỗi các ma trận Krylov. Tại sao nó đẹp ? Đơn giản là vì nó mở đường cho rất nhiều thuật toán nổi tiếng và các phương pháp tính toán nổi tiếng trong ma trận, một trong những nghành con có nhiều ứng dụng nhất trong đại số tuyến tính.
- 1951: decompositional approach for matrix computation của Alston Householder
Dân CS ai hẳn cũng nghe qua bài toán QR decomposition (tiếng Việt chuyên nghành của tôi hiện tại cực tệ, không nhớ nổi dịch thế nào nữa) hay bước đầu tiên trong thuật toán cùng tên nổi tiếng sử dụng để tính các eigenvalues and eigenvectors (vector riêng và giá trị riêng) của ma trận. Nhà toán học người Mỹ có cái tên rất đẹp Householder, đã phát minh ra một cách transformation (biến đổi) tuyến tính sau này mang tên ông giữa plane và hyperplane. Ứng dụng (again, vẻ đẹp của toán học là ứng dụng) của nó trong các nghành khoa học như CS hay Bioinformatics là không bút nào tả xiết, search trên pubmed hoặc google scholar nhiều vô số (tôi dự định có một serie về những ứng dụng của matrix computation trong sinh tin học nhưng không thể tìm được thời gian rảnh, hy vọng sau này học xong sẽ có
).



