Điều khiển và ứng dụng
   Tìm kiếmĐăng ký thành viên  >  Đăng nhập    Liên hệ  |  English    
  

Trang chủ



Các chuyên mục



 Cơ sở toán học chuyên ngành



1. Toán cơ bản
2. Tối ưu hóa ứng dụng



.Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (1)
.Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (2)
.Tính chất bài toán quy hoạch tuyến tính



3. Toán điều khiển



 Điều khiển tự động
 Phát hiện và chuẩn đoán lỗi
 Đo lường và điều khiển quá trình
 Phần tử thủy lực và khí nén
 Tính toán thời gian thực và phân phối
 Kỹ thuật điện - Điện tử - Điện tử công suất
 Truyền động điện và tự động hóa
 Kỹ thuật vi xử lý và DSP
 Robotics
 Kỹ thuật công nghệ phần mềm
 Các bài thực hành và thí nghiệm
 Mô hình hóa và mô phỏng
 Công nghệ điều khiển hàng hải
 Công nghệ điều khiển ô tô
 Ứng dụng GPS/GNSS và INS trong điều khiển
 Các đề tài nghiên cứu - ứng dụng



Thư viện trực tuyến



Tài liệu tham khảo
Tra cứu
Downloads



Thảo luận






http://www.thuvienkhoahoc.com

http://www.vinavigation.net

http://www.vagam.dieukhien.net





Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (1)

Nhân hai ma trận là phép tính cực kỳ cơ bản trong toán học. Thiết kế giải thuật nhân hai ma trận một cách hiệu quả là bài toán cực kỳ cơ bản trong KHMT. Tương tự như vậy, Discrete Fourier Transform (DFT - biến đổi Fourier rời rạc) là một trong những biến đổi toán học có cực kỳ nhiều ứng dụng thực tế, đặc biệt là trong xử lý tín hiệu số. Fast Fourier Transform (FFT) là một thuật toán tính DFT dùng phương pháp divide-and-conquer (chia để trị). FFT là một trong những thuật toán cơ bản nhất của KHMT. Lý thuyết nhóm (group theory) cũng cực kỳ hữu dụng trong KHMT, giúp ta giải các bài toán trong cryptography, trong thiết kế mạch, thiết kế expanding graphs, v.v.

Thế ba thứ này có liên quan gì đến nhau?

Một số bài báo gần đây của Henry Cohn, Christopher Umans, Robert Kleinberg, và Balázs Szegedy dùng DFT và group representation theory (lý thuyết biểu diễn nhóm) để thiết kế giải thuật nhân ma trận. Nhân cơ hội, tôi sẽ viết một series giới thiệu sơ bộ về cả ba nhánh này, và kết thúc bằng một combinatorial conjecture chưa ai giải được.

Trước hết, hãy nói về nhân ma trận. Để đơn giản ta chỉ xét các ma trận vuông  n \times n. Trong suốt một thời gian dài, người ta nghĩ rằng cần ít nhất  n^3 phép nhân để nhân hai ma trận  n \times n. Đến năm 1969, Volker Strassen - khi đó là một sinh viên ở MIT - nghĩ ra một thuật toán chia-để-trị chạy trong thời gian  O(n^{2.81}). Giải thuật này chính là giải thuật Strassen lừng danh; nó là một kết quả đột phá. Điểm thú vị là Strassen nghĩ ra lời giải này vì nó là bài tập trong một lớp ông đang học. Lúc nghĩ ra lời giải Strassen không biết là kết quả đó có ý nghĩa to lớn thế nào.

Từ đó trở đi, người ta cố gắng thiết kế các giải thuật chạy trong thời gian  O(n^\omega), trong đó  \omega tiến dần đến 2. Dĩ nhiên  n^2 là chặn dưới vì bản thân ma trận kết quả đã có đến  n^2 entries. Kết quả tốt nhất hiện nay là của Coppersmith và Winograd từ năm 1990, với  \omega = 2.376. Hiện nay thì người ta tin rằng  \omega có thể đạt đến  2+\epsilon với  \epsilon cho trước bất kỳ.

Tuy nhiên, suốt mười mấy năm trời kể từ bài báo của Coppersmith và Winograd vẫn chưa có kết quả gì mới. Năm 2003, Cohn và Umans tìm ra một cách khác để giải quyết vấn đề nhân ma trận này. Họ liên hệ nó với DFT và representation theory. Một bài báo mới của Cohn, Kleinberg, Szegedy, và Umans đăng ở hội nghị FOCS 2005 tháng 10 vừa qua phát triển hướng này sâu hơn, và họ đạt tới giới hạn của Coppersmith và Winograd dùng phương pháp mới này. Trong bài báo có hai conjectures mà giải được một trong chúng thì tương đương với việc chứng minh được có thể đạt đến  2+\epsilon với  \epsilon cho trước bất kỳ. Đạt đến đây sẽ là một kết quả đột phá lớn nhất trong tính toán matrix kể từ bài báo năm 1969 của Strassen.

--Ngô Quang Hưng--
Blog khoa học máy tính


Bookmark bài viết này:  del.icio.us  yahoo! myweb  Google  Windows Live  stumbleupon


Google
 
Copyright © 2005-2008
Designed by ca-group
All rights reserved



Những tài liệu trên trang web này có bản quyền thuộc nhóm Điều khiển Ứng dụng. Ngoài những tài liệu đã ghi rõ nguồn gốc xuất xứ, tất cả những tài liệu trên trang web này là công trình của các thành viên tham gia mà chưa từng công bố hoặc xuất bản ở một nơi nào khác. Các tác giả giữ bản quyền bài viết của chính mình và có toàn quyền gửi các bài viết của mình tham dự các hội nghị hoặc đăng trên các tạp chí khác. Nghiêm cấm mọi hình thức sao chép, lưu trữ và sử dụng tài liệu trên trang web ngoài mục đích giáo dục. Mọi trích dẫn đều phải ghi rõ nguồn CA Group: http://www.dieukhien.net. Mọi thư từ liên hệ xin gửi về: webmaster@dieukhien.net.

Bản quyền © 2005-2010 Điều khiển Ứng dụng. Copyright © 2005-2010 CA Group.