• E-mail: vted.net@gmail.com
Tuesday, August 9, 2022
  • HOME
  • CHUYÊN ĐỀ
    • Chuyên đề toán 10
    • Chuyên đề toán 11
    • Chuyên đề toán 12
    • Tài liệu ôn thi HSG Toán
    • Tài liệu ôn thi TN THPT
    • Tài liệu ôn thi ĐGNL
    • Tài liệu ôn thi vào 10
    • Tài liệu Casio
    • Công thức toán
  • TOÁN THCS
    • TOÁN 6
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 6
      • Giáo án Toán 6
    • TOÁN 7
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 7
      • Giáo án Toán 11
    • TOÁN 8
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 8
      • Giáo án Toán 8
    • TOÁN 9
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 9
      • Giáo án Toán 9
  • TOÁN THPT
    • TOÁN 10
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 10
      • Giáo án Toán 10
    • TOÁN 11
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 11
      • Giáo án Toán 11
    • TOÁN 12
      • Đề kiêm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 12
      • Giáo án Toán 12
  • TÀI LIỆU TOÁN
    • Blog Toán học
    • Toán cao cấp
    • Tạp chí Toán hoc Tuổi trẻ
    • Tạp chí Epsilon
    • Toán Tiếng Anh
  • ĐỀ THI TOÁN
    • Đề thi vào 10
    • Đề thi HSG
    • Đề thi ĐGNL
    • Đề thi thử THPT
    • Đề ôn thi THPT
  • THI ONLINE
    • Thi thử TN THPT môn Toán
No Result
View All Result
No Result
View All Result
Home Tài liệu Toán Blog Toán học

PHÉP NHÂN MA TRẬN TỪNG BƯỚC ĐẠT TỚI MỤC TIÊU LÝ TƯỞNG

vted by vted
08/01/2022
in Blog Toán học
Reading Time: 11 mins read
0

Các nhà toán học gần đây đã tiến được một bước gần hơn với mục tiêu “số mũ hai” của họ, tức là nhân một cặp ma trận cỡ nxn chỉ trong $n^2$ bước. Liệu họ có thể đạt được mục tiêu đó hay không?

Với các nhà khoa học máy tính và các nhà toán học, những đánh giá về “số mũ hai” là những kết quả quan trọng để ý thức về thế giới nên như thế nào?

“Thật khó để phân biệt tư duy khoa học với tư duy mơ mộng. Tôi muốn số mũ là hai vì nó đẹp.” – Chris Umans, Viện Công nghệ California cho biết: “Số mũ hai” đề cập đến ở đây là về tốc độ lý tưởng – về số bước cần thiết để thực hiện một trong những phép toán cơ bản nhất trong toán học: phép nhân ma trận. Nếu số mũ hai là có thể đạt được, ta có thể thực hiện phép nhân ma trận một cách nhanh nhất có thể về mặt vật lý. Còn nếu không, chúng ta đang mắc kẹt trong một thế giới có lẽ không phù hợp với giấc mơ của chúng ta.

Như chúng ta biết, ma trận là các mảng số. Khi có hai ma trận có kích thước tương thích, ta có thể nhân chúng để tạo ra ma trận thứ ba. Ví dụ: nếu bắt đầu với một cặp ma trận 2×2, ta sẽ tính được tích của chúng và kết quả cũng sẽ là ma trận 2×2, gồm 4 phần tử . Tổng quát hơn ta cũng có tích của một hai ma trận cỡ nxn cũng là một ma trận cỡ nxn với $n^2$ phần tử.

Chính vì lý do này, người ta hy vọng rằng ta có thể nhân các cặp ma trận cỡ nxn trong $n^2$ bước – tức là với số bước chỉ cần viết ra câu trả lời cho các phần tử của ma trận. Đây cũng là nơi xuất phát của “số mũ hai”.

Và trong khi không ai biết chắc liệu có thể đạt được điều đó hay không thì các nhà nghiên cứu vẫn tiếp tục đạt được những tiến bộ theo hướng này.

Một bài báo được đăng vào gần nhất vào tháng 10 năm 2020, mô tả phương pháp nhanh nhất từ trước đến nay để nhân hai ma trận với nhau. Kết quả là của Josh Alman , một nhà nghiên cứu sau tiến sĩ tại Đại học Harvard, và Virginia Vassilevska Williams thuộc Viện Công nghệ Massachusetts: sai lệch về số mũ đã giảm đi khoảng một phần trăm nghìn so với số mũ tốt nhất trước đó. Đó là điển hình của một trong những thành tựu gần đây trong lĩnh vực này.

Để hiểu rõ quá trình và cách cải thiện quá trình này, ta hãy bắt đầu với một cặp ma trận 2×2, A và B. Khi tính toán từng phần tử của ma trận tích, ta sử dụng hàng tương ứng của A và cột tương ứng của B. Vì vậy, để có phần tử trên cùng bên phải, ta nhân số đầu tiên ở hàng đầu tiên của A với số đầu tiên ở cột thứ hai của B, sau đó nhân số thứ hai ở hàng đầu tiên của A với số thứ hai trong cột thứ hai của B, và cộng hai kết quả đó với nhau.

Thao tác này được gọi là lấy “tích trong” của một hàng với một cột. Để tính toán các phần tử khác trong ma trận tích, ta lặp lại quy trình với các hàng và cột tương ứng.Nhìn chung, phương pháp để nhân hai ma trận 2×2 này cần dùng đến 8 phép nhân với một số phép cộng và tổng quát hơn, theo cách này để nhân 2 ma trận cỡ nxn ta sẽ cần dùng tới $n^3$ phép nhân và một số phép cộng.

Tuy nhiên, khi ma trận với kích cỡ lớn hơn, số phép nhân cần dùng để tính tích của chúng tăng nhanh hơn nhiều so với số phép cộng. Trong khi ta cần 8 phép nhân trung gian để tìm tích của 2 ma trận 2×2, thì lại cần tới 64 phép nhân để tích của 2 ma trận 4×4. Số lượng phép cộng cần dùng để tính thì lại gần nhau hơn nhiều. Số phép cộng mà ta cần dùng bằng số lượng các phần tử trong ma trận tích, tức là cần 4 phép cộng với ma trận 2×2 và 16 với ma trận 4×4. Sự khác biệt giữa phép cộng và phép nhân này cũng giải thích lý do tại sao các nhà nghiên cứu thường sẽ đo tốc độ của phép nhân ma trận hoàn toàn dựa trên số lượng các phép nhân.

“Các phép nhân là tất cả,” Umans nói. “Số mũ trên thời gian chạy cuối cùng chỉ hoàn toàn phụ thuộc vào số phép nhân. Các phép cộng gần như là sẽ biến mất. “

Trong nhiều thế kỷ, người ta nghĩ rằng $n^3$ đơn giản là thời gian nhanh nhất mà ta có thể thực hiện được. Vào năm 1969, Volker Strassen được cho là đã chứng minh rằng không có cách nào để nhân ma trận 2×2 bằng cách sử dụng ít hơn 8 phép nhân. Nhưng rõ ràng anh ta không thể tìm được cách chứng minh, và sau một thời gian anh ta nhận ra rằng: Thực ra có một cách để làm điều đó với 7!

Strassen đã đưa ra ý tưởng với một tập hợp các mối quan hệ phức tạp để có thể thay thế một trong 8 phép nhân đó bằng 14 phép cộng bổ sung. Điều đó nghe có vẻ không có nhiều khác biệt, nhưng nó dẫn đến những kết quả thành công nhờ tầm quan trọng của phép nhân so với phép cộng. Và bằng việc tìm ra cách để lưu một phép nhân đơn lẻ cho các ma trận nhỏ 2×2, Strassen đã tìm ra một lỗ hổng mà anh ta có thể khai thác được khi nhân các ma trận lớn hơn.Vassilevska Williams nói: “Cải tiến nhỏ này dẫn đến những cải tiến lớn với những ma trận lớn.”

Ví dụ: Giả sử ta muốn nhân một cặp ma trận 8×8. Một cách để làm điều đó là ta chia mỗi ma trận lớn thành bốn ma trận 4×4, khi đó 2 ma trận 8×8 ban đầu được coi như là 2 ma trận 2×2, ở đó mỗi ma trận 2×2 thì có 4 phần tử, mỗi phần tử là một ma trận 4×4. Thông qua một số thao tác này, ta lại có thể chia bản thân mỗi ma trận 4×4 thành bốn ma trận 2×2.

MA TRẬN
https://vted.net/
ma trận
https://vted.net/

Ưu điểm của sự giảm thiểu này là liên tục chia nhỏ các ma trận lớn hơn thành các ma trận nhỏ hơn – là có thể áp dụng thuật toán Strassen lặp đi lặp lại cho các ma trận nhỏ hơn, và rõ ràng sẽ tiết kiệm được thời gian ở mỗi bước. Và thuật toán của Strassen đã cải thiện tốc độ của phép nhân ma trận từ $n^3$ thành $n^{2.81}$ phép tính nhân.

Cải tiến lớn tiếp theo là vào cuối những năm 1970, với một cách thức cơ bản là mới để tiếp cận vấn đề. Nó liên quan đến việc chuyển phép nhân ma trận thành một bài toán tính toán khác trong đại số tuyến tính liên quan đến các đối tượng được gọi là tensors. Các tensors đặc biệt được sử dụng trong bài toán này là các mảng ba chiều gồm nhiều phần khác nhau, mỗi phần trông giống như một bài toán nhân ma trận nhỏ.

Phép nhân ma trận và bài toán liên quan đến các tensors tương đương với nhau theo một nghĩa nào đó, nhưng các nhà nghiên cứu đã có các cách làm nhanh hơn để giải quyết bài toán sau. Điều này khiến họ phải xác định tỉ lệ tương ứng giữa hai ma trận: Bạn có thể nhân ma trận lớn đến mức nào để có cùng một chi phí tính toán mà nó cần để giải bài toán tensor?“

Đây là một mô hình rất phổ biến trong khoa học máy tính lý thuyết, về việc giảm bớt giữa các vấn đề để cho thấy chúng dễ hoặc khó như nhau,” Alman nói.

Năm 1981, Arnold Schönhage đã sử dụng phương pháp này để chứng minh rằng có thể thực hiện phép nhân ma trận với $n^{2.522}$ phép tính nhân. Strassen sau đó gọi cách tiếp cận này là “phương pháp laser”.

Trong vài thập kỷ qua, mọi cải tiến trong phép nhân ma trận đều đến từ những cải tiến trong phương pháp laser, do các nhà nghiên cứu đã tìm ra những giải pháp ngày càng hiệu quả để chuyển đổi giữa hai vấn đề. Trong chứng minh mới của họ, Alman và Vassilevska Williams đã giảm bớt mâu thuẫn giữa hai bài toán và cho thấy rằng có thể “mua” nhiều phép nhân ma trận hơn mức đã nhận ra trước đây để giải một bài toán tensor có kích thước nhất định.

Henry Cohn của Microsoft Research cho biết: “Về cơ bản Josh và Virginia đã tìm ra cách sử dụng máy móc bên trong phương pháp laser và điều chỉnh nó để thu được kết quả tốt hơn”.Bài báo đã cải thiện giới hạn tốc độ lý thuyết trên phép nhân ma trận thành $n^{2,3728596}$ .

Điều này giúp Vassilevska Williams “giành lại vương miện” trong cuộc đua về thời gian nhân ma trận, mà trước đó cô đã nắm giữ vào năm 2012 ( $n^{2,372873}$ ), sau đó bị mất vào năm 2014 vào tay François Le Gall ( $n^{2,3728639}$ ).

Tất nhiên câu chuyện giành lại vương miện chỉ là trò đùa nhưng rõ ràng cách tiếp cận này đang giảm dần thời gian tính toán. Trên thực tế, sự cải tiến của Alman và Vassilevska Williams có thể đã đạt được hiệu quả gần như tối đa của phương pháp laser – tuy còn thiếu xa so với mục tiêu lý tưởng cuối cùng.

“Không có khả năng có một bước nhảy vọt để tính lũy thừa hai bằng cách sử dụng phương pháp cụ thể này,” Umans nói.

Có lẽ để đạt được điều đó, chúng ta sẽ phải khám phá các phương pháp mới và duy trì niềm tin rằng điều đó là có thể. Và … biết đâu một ngày nào đó kì tích sẽ xuất hiện !?!

Bài viết tham khảo tại: https://www.quantamagazine.org/mathematicians-inch…/

Related Posts

460 BÀI TOÁN VUI LUYỆN TRÍ THÔNG MINH
Blog Toán học

460 BÀI TOÁN VUI LUYỆN TRÍ THÔNG MINH

04/06/2022
PHƯƠNG PHÁP QUY NẠP TOÁN HỌC
Blog Toán học

PHƯƠNG PHÁP QUY NẠP TOÁN HỌC

09/04/2022
CHUYÊN KHẢO ĐA THỨC
Blog Toán học

CHUYÊN KHẢO ĐA THỨC

07/04/2022
CÁC BÀI TẬP VÀ CHUYÊN ĐỀ TAM GIÁC ĐỒNG DẠNG
Blog Toán học

CÁC BÀI TẬP VÀ CHUYÊN ĐỀ TAM GIÁC ĐỒNG DẠNG

07/04/2022

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Search

No Result
View All Result

Recent Posts

  • Chuyên đề trắc nghiệm mặt trụ, hình trụ và khối trụ
  • Chuyên đề trắc nghiệm mặt nón, hình nón và khối nón
  • Bài toán thực tế hình học không gian
  • Chuyên đề trắc nghiệm tính đơn điệu của hàm số
  • Chuyên đề trắc nghiệm cực trị của hàm số
  • Chuyên đề trắc nghiệm giá trị lớn nhất và nhỏ nhất của hàm số
  • Chuyên đề trắc nghiệm đường tiệm cận của đồ thị hàm số
  • Chuyên đề trắc nghiệm nhận dạng đồ thị hàm số
  • Bài toán biện luận số nghiệm phương trình
  • Bài toán tương giao giữa hai đồ thị

Tag

BLOG TOÁN HỌC CHUYÊN ĐỀ HÀM SỐ CHỈ TIÊU TUYỂN SINH GIÁO ÁN TOÁN 10 GIÁO ÁN TOÁN 11 GIÁO ÁN TOÁN 12 KHỐI ĐA DIỆN Nghị luận xã hội NGUYÊN HÀM - TÍCH PHÂN NGỮ VĂN 9 NGỮ VĂN 12 PHƯƠNG THỨC XÉT TUYỂN QUAN HỆ VUÔNG GÓC SÁCH GIÁO KHOA THI THỬ ONLINE THI THỬ TN THPT 2022 Thi thử TN THPT 2021 TIN TỨC TOÁN 10 TOÁN 11 TOÁN 12 TOÁN TIẾNG ANH TRẮC NGHIỆM XÁC SUẤT TUYỂN SINH LỚP 10 TUYỂN SINH ĐH 2022 TUYỂN SINH ĐẠI HỌC TÀI LIỆU ÔN THI THPTQG TẠP CHÍ EPSILON ÔN THI ĐGNL ĐỀ KSCL TOÁN 10 ĐỀ KSCL TOÁN 11 ĐỀ KSCL TOÁN 12 ĐỀ THI GIỮA HK2 TOÁN 10 ĐỀ THI GIỮA HK2 TOÁN 11 ĐỀ THI GIỮA HK2 TOÁN 12 ĐỀ THI HK2 TOÁN 10 ĐỀ THI HK2 TOÁN 11 ĐỀ THI HK2 TOÁN 12 ĐỀ THI HSG TOÁN 11 ĐỀ THI HSG TOÁN 12 ĐỀ THI THPT MÔN TOÁN CHÍNH THỨC ĐỀ THI THỬ ĐỀ THI THỬ 2022 ĐỀ THI ĐGNL ĐỀ ÔN THI TN THPT

About Us

VTED

Một thư viện online nơi bạn có thể tải xuống các tài liệu, đề thi, giáo trình, ebook, sách... môn Toán hấp dẫn, hot, nổi bật với các loại file pdf, word, excel, powerpoint... miễn phí.

Recent Posts

  • Chuyên đề trắc nghiệm mặt trụ, hình trụ và khối trụ
  • Chuyên đề trắc nghiệm mặt nón, hình nón và khối nón
  • Bài toán thực tế hình học không gian

Fanpage

Tài liệu Toán THPT
  • Giới Thiệu
  • Liên Hệ
  • Bản Quyền

Copyright © 2022 | Bản quyền thuộc về BKTaiLieu.com

No Result
View All Result
  • HOME
  • CHUYÊN ĐỀ
    • Chuyên đề toán 10
    • Chuyên đề toán 11
    • Chuyên đề toán 12
    • Tài liệu ôn thi HSG Toán
    • Tài liệu ôn thi TN THPT
    • Tài liệu ôn thi ĐGNL
    • Tài liệu ôn thi vào 10
    • Tài liệu Casio
    • Công thức toán
  • TOÁN THCS
    • TOÁN 6
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 6
      • Giáo án Toán 6
    • TOÁN 7
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 7
      • Giáo án Toán 11
    • TOÁN 8
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 8
      • Giáo án Toán 8
    • TOÁN 9
      • Tài liệu học tập
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Đề thi HSG
      • Bài tập toán 9
      • Giáo án Toán 9
  • TOÁN THPT
    • TOÁN 10
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 10
      • Giáo án Toán 10
    • TOÁN 11
      • Đề kiểm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 11
      • Giáo án Toán 11
    • TOÁN 12
      • Đề kiêm tra
      • Đề thi giữa HK1
      • Đề thi HK1
      • Đề thi giữa HK2
      • Đề thi HK2
      • Đề thi khảo sát
      • Tài liệu học tập
      • Bài tập toán 12
      • Giáo án Toán 12
  • TÀI LIỆU TOÁN
    • Blog Toán học
    • Toán cao cấp
    • Tạp chí Toán hoc Tuổi trẻ
    • Tạp chí Epsilon
    • Toán Tiếng Anh
  • ĐỀ THI TOÁN
    • Đề thi vào 10
    • Đề thi HSG
    • Đề thi ĐGNL
    • Đề thi thử THPT
    • Đề ôn thi THPT
  • THI ONLINE
    • Thi thử TN THPT môn Toán

Copyright © 2022 | Bản quyền thuộc về BKTaiLieu.com