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 \omega 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.

Chủ đề : Thuật ToánBookmark the permalink. Trackbacks are closed, but you can post a comment.

6 Comments

  1. manhtranlinh
    Posted 08/01/2007 at 8:43 am | Permalink

    Em vẫn chưa hiểu được, từ con đường nào mà Strassen có thể nghĩ ra giải thuật trên :( Bác nào dẫn dắt hộ em với :)

  2. diep_nv
    Posted 14/06/2007 at 12:06 pm | Permalink

    Có anh chị nào có Source của 2 thuật toán DFT và FFT ( Viết bằng C thì càng tốt ) thì cho em xin với nhé, hiện tại em đang rất cần. Thanksss
    ____________________________

    Email: nguyendiepcntt@gmail.com

  3. dongta
    Posted 27/07/2007 at 12:45 pm | Permalink

    Matrix multiplications xuất hiện rất nhiều (và chủ yếu) trong các bài toán lý (ví dụ khi giải một PDE). Do bản chất vật lý nên đa số các ma trận arise là sparse matrices. Intuitively, nếu A[i,j] biểu diễn potential giữa x_i và x_j thì matrix A is very dense diagonally (theoretically, A[i,i] is singular: potential giữa 2 particles cùng 1 vị trí là infinity) and sparse off-diagonal, relatively. Đối với những ma trận như vậy thì Axb, where b is an arbitrary vector, chỉ take n*log(n) time bằng Fast Multipole Method (FMM).

    Thực tế, FMM (discovered by L. Greengard and V. Rokhlin) là một thuật toán rất nổi tiếng trong Scientific Computing. Bài báo của 2 người này 1300+ citations, outnumbers the number of citations of ones by Coppersmith-Winograd and Strassen.

    Tất nhiên, trong những bài toán mà mình phải nhân 2 ma trận arbitrary thì Coppersmith-Winograd is the choice.

  4. Posted 27/07/2007 at 7:23 pm | Permalink

    Thật ra các thuật toán của Strassen và Coppersmith-Winograd có giá trị lý thuyết là chính, chẳng ai dùng chúng nhân các ma trận lớn trên thực tế: hidden-constant lớn quá, implement phức tạp dễ bị lỗi.

    Matrix multiplications xuất hiện nhiều nhất trong computer graphics (games, animations, etc.). Pretty much every movement is a transformation! Tưởng tượng trên thế giới có biết bao nhiêu người chơi game mỗi ngày, và các bộ vi xử lý và phần mềm chuyên về graphics sẽ phải làm biết bao nhiêu phép nhân ma trận hàng ngày.

  5. dongta
    Posted 27/07/2007 at 8:08 pm | Permalink

    Không có gì nghi ngờ rằng matrix multiplications dùng rất nhiều trong computer graphics. Nhưng những matrix này thường bé và computations are normally done on a single PC (e.g. games, animations).

    Cái em muốn nói ở đây là huge matrix multiplications và thường run on super-computers. Đối với những matrix như vậy, asymptotic bound mới thật sự quan trọng (và rất quan trọng). Insane matrices như vậy thường come up khi simulate multiscale physical systems. Đa số các supercomputers nhanh nhất thế giới (http://en.wikipedia.org/wiki/TOP500) đều được đặt tại các national labs và các viện tính toán, chủ yếu dùng để mô phỏng thời tiết, khí tượng, động đất, or molecular simulations.

    Huge matrix multiplications cũng hay come up in computational visualization; hoặc trong games (nếu resolution is very high). Nhưng khi làm games thì các lập trình viên không thể assume rằng user sẽ phải chơi game của mình trên 100 parallel CPUs.

  6. chi
    Posted 11/05/2009 at 5:47 am | Permalink

    the khong co code cua bai nay ah?

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>