Các nhà khoa học máy tính là một nhóm có yêu cầu cao. Đối với họ, việc có được câu trả lời đúng cho một vấn đề là chưa đủ - mục tiêu hầu như luôn luôn là có được câu trả lời hiệu quả nhất có thể.

Thực hiện phép nhân ma trận hoặc mảng số. Năm 1812, nhà toán học người Pháp Jacques Philippe Marie Binet đã đưa ra bộ quy tắc cơ bản mà chúng ta vẫn dạy cho học sinh. Nó hoạt động hoàn toàn tốt, nhưng các nhà toán học khác đã tìm ra cách đơn giản hóa và tăng tốc quá trình. Bây giờ nhiệm vụ của đẩy nhanh quá trình Phép nhân ma trận nằm ở điểm giao thoa giữa toán học và khoa học máy tính, nơi các nhà nghiên cứu tiếp tục cải tiến quy trình cho đến ngày nay - mặc dù trong những thập kỷ gần đây, mức tăng đạt được khá khiêm tốn. Kể từ năm 1987, những cải tiến về mặt số học trong phép nhân ma trận là “nhỏ và… cực kỳ khó đạt được”, cho biết. François Le Gall, một nhà khoa học máy tính tại Đại học Nagoya.

Giờ đây, ba nhà nghiên cứu – Ran Duan và Renfei Zhou của Đại học Thanh Hoa và Hongxun Wu của Đại học California, Berkeley – đã thực hiện một bước tiến lớn trong việc giải quyết vấn đề lâu năm này. Của họ kết quả mớiLe Gall cho biết, được trình bày vào tháng 11 năm ngoái tại hội nghị Nền tảng Khoa học Máy tính, xuất phát từ một kỹ thuật mới bất ngờ. Mặc dù bản thân sự cải tiến này tương đối nhỏ nhưng Le Gall gọi nó là “lớn hơn về mặt khái niệm so với những cải tiến khác trước đó”.

Kỹ thuật này tiết lộ một nguồn cải tiến tiềm năng chưa được biết đến trước đây và do đó chưa được khai thác và nó đã mang lại kết quả: Tờ giấy thứ hai, được xuất bản vào tháng 1, được xây dựng dựa trên tài liệu đầu tiên cho thấy phép nhân ma trận có thể được tăng cường hơn nữa như thế nào.

“Đây là một bước đột phá lớn về mặt kỹ thuật,” nói William Kuszmaul, một nhà khoa học máy tính lý thuyết tại Đại học Harvard. “Đây là cải tiến lớn nhất trong phép nhân ma trận mà chúng tôi từng thấy trong hơn một thập kỷ.”

Nhập ma trận

Nó có vẻ như là một vấn đề khó hiểu, nhưng phép nhân ma trận là một phép toán cơ bản. Nó được tích hợp vào phần lớn các thuật toán mà mọi người sử dụng hàng ngày cho nhiều nhiệm vụ khác nhau, từ hiển thị đồ họa máy tính sắc nét hơn đến giải quyết các vấn đề hậu cần trong lý thuyết mạng. Và cũng như trong các lĩnh vực tính toán khác, tốc độ là điều tối quan trọng. Ngay cả những cải tiến nhỏ cuối cùng cũng có thể giúp tiết kiệm đáng kể thời gian, sức mạnh tính toán và tiền bạc. Nhưng hiện nay, các nhà lý thuyết chủ yếu quan tâm đến việc tìm hiểu xem quá trình này có thể diễn ra nhanh đến mức nào.

Cách nhân hai truyền thống n-bởi-n ma trận - bằng cách nhân các số ở mỗi hàng trong ma trận đầu tiên với các số ở các cột ở ma trận thứ hai - yêu cầu n³ phép nhân riêng biệt. Đối với ma trận 2 x 2, điều đó có nghĩa là 2³ hoặc 8 phép nhân.

Năm 1969, nhà toán học Volker Strassen đã tiết lộ một quy trình phức tạp hơn có thể nhân các ma trận 2 x 2 chỉ trong bảy bước nhân và 18 phép cộng. Hai năm sau, nhà khoa học máy tính Shmuel Winograd đã chứng minh rằng 2 thực sự là mức tối thiểu tuyệt đối cho ma trận 2 x XNUMX.

Strassen đã khai thác ý tưởng tương tự để chứng tỏ rằng tất cả các n-bởi-n ma trận cũng có thể được nhân với thời gian ít hơn n³ các bước. Yếu tố chính trong chiến lược này bao gồm một quy trình gọi là phân rã - chia một ma trận lớn thành các ma trận con nhỏ hơn liên tiếp, có thể nhỏ đến mức 2 x 2 hoặc thậm chí 1 x 1 (đây chỉ là các số đơn lẻ).

Lý do cơ bản để chia một mảng khổng lồ thành các phần nhỏ khá đơn giản, theo Virginia Vassilevska Williams, một nhà khoa học máy tính tại Viện Công nghệ Massachusetts và là đồng tác giả của một trong những bài báo mới. Vassilevska Williams nói: “Thật khó để con người nhìn vào một ma trận lớn (ví dụ theo thứ tự 100 x 100) và nghĩ ra thuật toán tốt nhất có thể. Ngay cả ma trận 3 x 3 vẫn chưa được giải quyết hoàn toàn. “Tuy nhiên, người ta có thể sử dụng thuật toán nhanh mà người ta đã phát triển cho các ma trận nhỏ để thu được thuật toán nhanh cho các ma trận lớn hơn.”

Các nhà nghiên cứu đã xác định rằng chìa khóa của tốc độ là giảm số bước nhân, hạ số mũ đó từ n³ (đối với phương pháp tiêu chuẩn) nhiều nhất có thể. Giá trị thấp nhất có thể, n², về cơ bản là chỉ cần viết câu trả lời. Các nhà khoa học máy tính gọi số mũ đó là omega, ω, với n^ω là số bước cần thiết ít nhất có thể để nhân thành công hai n-bởi-n ma trận như n phát triển rất lớn. Chu, người cũng là đồng tác giả của bài báo tháng 2024 năm 2, cho biết: “Mục đích của công việc này là để xem bạn có thể tiến gần đến mức XNUMX đến mức nào và liệu nó có thể đạt được về mặt lý thuyết hay không”.

Tiêu điểm bằng tia Laser

Năm 1986, Strassen có một bước đột phá lớn khác khi ông giới thiệu cái được gọi là phương pháp laser để nhân ma trận. Strassen đã sử dụng nó để thiết lập giá trị trên cho omega là 2.48. Mặc dù phương pháp này chỉ là một bước trong phép nhân ma trận lớn nhưng đây là một trong những bước quan trọng nhất vì các nhà nghiên cứu đã tiếp tục cải tiến nó.

Một năm sau, Winograd và Don Coppersmith giới thiệu một thuật toán mới bổ sung hoàn hảo cho phương pháp laser. Sự kết hợp các công cụ này đã góp phần vào hầu hết các nỗ lực tiếp theo nhằm tăng tốc độ nhân ma trận.

Đây là một cách suy nghĩ đơn giản về cách các yếu tố khác nhau này kết hợp với nhau. Hãy bắt đầu với hai ma trận lớn A và B mà bạn muốn nhân với nhau. Đầu tiên, bạn phân tách chúng thành nhiều ma trận con hoặc khối nhỏ hơn, như đôi khi chúng được gọi. Tiếp theo, bạn có thể sử dụng thuật toán của Coppersmith và Winograd để đóng vai trò như một loại hướng dẫn sử dụng để xử lý và cuối cùng là lắp ráp các khối. Vassilevska Williams cho biết: “Nó cho tôi biết cần nhân những gì, thêm những gì và những mục nào sẽ đi đến đâu” trong ma trận tích C. “Đó chỉ là một công thức để xây dựng C từ A và B.”

Tuy nhiên, có một nhược điểm: Đôi khi bạn kết thúc với các khối có các mục chung. Việc để những mục này trong sản phẩm sẽ giống như việc đếm các mục đó hai lần, do đó, tại một thời điểm nào đó, bạn cần loại bỏ những thuật ngữ trùng lặp đó, được gọi là phần trùng lặp. Các nhà nghiên cứu thực hiện điều này bằng cách “loại bỏ” các khối chứa chúng — đặt các thành phần của chúng bằng 0 để loại bỏ chúng khỏi phép tính.

Đó là lúc phương pháp laser của Strassen cuối cùng phát huy tác dụng. Le Gall cho biết: “Phương pháp laser thường hoạt động rất tốt và thường tìm ra cách tốt để tiêu diệt một tập hợp con các khối nhằm loại bỏ sự chồng chéo”. Sau khi tia laser đã loại bỏ hoặc “đốt cháy” tất cả các phần chồng chéo, bạn có thể xây dựng ma trận sản phẩm cuối cùng, C.

Việc kết hợp các kỹ thuật khác nhau này lại với nhau sẽ tạo ra một thuật toán nhân hai ma trận với tổng số phép nhân cố ý eo hẹp - ít nhất là về mặt lý thuyết. Phương pháp laser không nhằm mục đích thực tế; đó chỉ là một cách nghĩ về cách lý tưởng để nhân ma trận. “Chúng tôi không bao giờ chạy phương pháp này [trên máy tính],” Chu nói. “Chúng tôi phân tích nó.”

Và phân tích đó là nguyên nhân dẫn đến sự cải thiện lớn nhất đối với omega trong hơn một thập kỷ.

Một mất mát được tìm thấy

Bài báo mùa hè năm ngoái của Duan, Chu và Wu cho thấy quá trình của Strassen vẫn có thể được đẩy nhanh đáng kể. Tất cả là do một khái niệm mà họ gọi là sự mất mát tiềm ẩn, được chôn sâu trong các phân tích trước đó – “kết quả của việc vô tình giết chết quá nhiều khối”, Chu nói.

Phương pháp laser hoạt động bằng cách dán nhãn các khối có phần chồng lên nhau là rác, dự kiến ​​​​sẽ được xử lý; các khối khác được coi là xứng đáng và sẽ được lưu. Tuy nhiên, quá trình lựa chọn có phần ngẫu nhiên. Trên thực tế, một khối được đánh giá là rác có thể trở nên hữu ích. Đây không phải là điều hoàn toàn bất ngờ, nhưng bằng cách kiểm tra nhiều lựa chọn ngẫu nhiên này, nhóm của Duan đã xác định rằng phương pháp laser đang đánh giá thấp các khối một cách có hệ thống: Cần lưu lại nhiều khối hơn và ít khối bị vứt đi hơn. Và, như thường lệ, ít lãng phí hơn sẽ mang lại hiệu quả cao hơn.

Le Gall cho biết: “Việc có thể giữ nhiều khối hơn mà không bị chồng chéo sẽ dẫn đến… thuật toán nhân ma trận nhanh hơn”.

Sau khi chứng minh sự tồn tại của sự mất mát này, nhóm của Duan đã sửa đổi cách dán nhãn các khối bằng phương pháp laser, giúp giảm đáng kể chất thải. Kết quả là, họ đặt ra giới hạn trên mới cho omega vào khoảng 2.371866 - một sự cải thiện so với giới hạn trên trước đó là 2.3728596, thiết lập vào năm 2020 của Josh Alman và Vassilevska Williams. Đó có vẻ là một sự thay đổi khiêm tốn, hạ thấp giới hạn xuống chỉ khoảng 0.001. Nhưng đó là cải tiến lớn nhất mà các nhà khoa học từng thấy kể từ năm 2010. Khi so sánh, kết quả năm 2020 của Vassilevska Williams và Alman chỉ cải thiện so với kết quả tiền nhiệm là 0.00001.

Nhưng điều thú vị nhất đối với các nhà nghiên cứu không chỉ là bản thân kỷ lục mới - nó không tồn tại được lâu. Thực tế là bài báo đã tiết lộ một con đường cải tiến mới mà cho đến lúc đó vẫn hoàn toàn không được chú ý. Le Gall cho biết trong gần bốn thập kỷ, mọi người đều dựa vào cùng một phương pháp laser. “Rồi họ nhận ra rằng, chúng tôi có thể làm tốt hơn.”

Bài báo tháng 2024 năm 2.371552 đã cải tiến cách tiếp cận mới này, cho phép Vassilevska Williams, Chu và các đồng tác giả của họ giảm thiểu hơn nữa tổn thất tiềm ẩn. Điều này dẫn đến sự cải thiện thêm về giới hạn trên của omega, giảm nó xuống còn XNUMX. Các tác giả cũng khái quát hóa kỹ thuật tương tự để cải thiện quá trình nhân cho hình chữ nhật (n-bởi-m) ma trận - một thủ tục có ứng dụng trong lý thuyết đồ thị, học máy và các lĩnh vực khác.

Một số tiến bộ hơn nữa theo hướng này là gần như chắc chắn, nhưng vẫn có những giới hạn. Năm 2015, Le Gall và hai cộng tác viên chứng minh rằng phương pháp hiện tại – phương pháp laser kết hợp với công thức Coppersmith-Winograd – không thể mang lại omega dưới 2.3078. Để thực hiện thêm bất kỳ cải tiến nào, Le Gall cho biết, “bạn cần cải tiến [cách tiếp cận] ban đầu của Coppersmith và Winograd vốn chưa thực sự thay đổi kể từ năm 1987". Nhưng cho đến nay vẫn chưa có ai nghĩ ra cách nào tốt hơn. Có thể thậm chí không có một.

“Cải thiện omega thực sự là một phần để hiểu được vấn đề này,” Chu nói. “Nếu chúng ta có thể hiểu rõ vấn đề thì chúng ta có thể thiết kế các thuật toán tốt hơn cho nó. [Và] mọi người vẫn đang ở giai đoạn đầu của sự hiểu biết về vấn đề lâu đời này.”