Tối ưu hóa một tập hợp các đa thức cho tốc độ tính toán

Question

Tôi có một tập hợp các biểu thức đa thức được tạo ra bởi hệ thống đại số máy tính (CAS). Ví dụ, đây là một phần tử của tập hợp này.

-d * d * l * l * qb * b * l * l * q * 2 * d * f * j * l * q + 2 * b * f * h * l * qf * f * j * j * qb * b * j * j * q + 2 * b * d * h * j * qf * f * h * h * qd * d * h * h * q + b * b * j * j * o * o-2 * b * d * h * j * o * o + d * d * h * h * o * o-2 * b * b * j * l * n * o + 2 * b * d * h * l * n * o + 2 * b * f * h * j * n * o-2 * d * f * h * h * n * o + 2 * b * d * j * l * m * o-2 * d * d * h * l * m * o-2 * b * f * j * j * m * o + 2 * d * f * h * j * m * o + b * b * l * l * n * n-2 * b * f * h * l * n * n + f * f * h * h * n * n-2 * b * d * l * l * m * n + 2 * b * f * j * l * m * n + 2 * d * f * h * l * m * n * 2 * f * f * h * j * m * n + d * d * l * l * m * m-2 * d * f * j * l * m * m + f * f * j * j * m * m

Tôi cần thực hiện tất cả chúng trong chương trình C càng nhanh càng tốt. Nếu bạn nhìn kỹ vào bất kỳ công thức nào trong số này, rõ ràng là chúng ta có thể tối ưu hóa chúng cho tốc độ tính toán. Ví dụ, trong đa thức được dán ở trên, tôi có thể thấy ngay các thuật ngữ -d * d * l * l * q, 2 * d * f * j * l * q và -f * f * j * j * q, để tôi có thể thay thế tổng của họ bằng -q * square (d * lf * j). Tôi tin rằng có rất nhiều thứ như vậy có thể được thực hiện ở đây. Tôi không tin (nhưng có lẽ tôi là sai) rằng bất kỳ trình biên dịch sẽ có thể tìm thấy tối ưu hóa này, hoặc có lẽ những người tiên tiến hơn. Tôi đã cố gắng yêu cầu maxima (một CAS) để làm điều này cho tôi, nhưng không có gì xuất hiện (vì tôi là một người mới bắt đầu với maxima, tôi có lẽ đã bỏ lỡ một lệnh ma thuật). Vì vậy, câu hỏi đầu tiên của tôi là: công cụ/thuật toán nào chúng ta có thể sử dụng để tối ưu hóa một biểu thức đa thức cho tốc độ tính toán?

Khi nói đến tối ưu hóa một tập hợp các biểu thức đa thức chia sẻ hầu hết các biến của chúng, mọi thứ trở nên phức tạp hơn. Thật vậy, tối ưu hóa biểu thức bằng biểu thức có thể tối ưu bởi vì các phần phổ biến có thể được trình biên dịch xác định trước khi tối ưu hóa nhưng không còn nữa sau khi điều này không được thực hiện như một tổng thể. Vì vậy, câu hỏi thứ hai của tôi là: công cụ/thuật toán nào chúng ta có thể sử dụng để tối ưu hóa một tập hợp các biểu thức đa thức cho tốc độ tính toán?

Trân trọng,

P.S. : bài đăng này chia sẻ một số điểm tương đồng với "computer algebra soft to minimize the number of operations in a set of polynomials", tuy nhiên câu trả lời được đưa ra trong đó một điểm cho các chương trình CAS thay vì nói cách chúng tôi có thể sử dụng chúng để đạt được mục tiêu của chúng tôi.

Answer 1

Là một nỗ lực đầu tiên, tôi có thể thử cách tiếp cận tham lam.

Vì vậy, sử dụng ví dụ đầu tiên của bạn, chúng tôi bắt đầu với điều này:

-1*d*d*l*l*q 
-1*b*b*l*l*q 
    2*d*f*j*l*q 
    2*b*f*h*l*q 
-1*f*f*j*j*q 
... 

Bây giờ cố gắng để tìm ra mô hình lặp đi lặp lại hầu hết trong các điều khoản. Đây là q, may mắn xuất hiện trong tất cả chúng. Hãy loại bỏ nó và rằng lá chúng tôi với

-1*d*d*l*l 
-1*b*b*l*l 
    2*d*f*j*l 
    2*b*f*h*l 
-1*f*f*j*j 
... 

Bây giờ làm điều tương tự một lần nữa, lần này chúng tôi nhận l và vấn đề chia tách thành hai bài toán.

-1*d*d*l 
-1*b*b*l 
    2*d*f*j 
    2*b*f*h 
    --------- 
-1*f*f*j*j 
... 

Lặp lại một cách đệ quy cho đến khi không có sự lặp lại trái và truy tìm các bước của bạn sao bạn đệ quy có thể tái tạo lại một phiên bản đơn giản của biểu thức:

q*(l*<first subproblem>+<second subproblem>) 

Như bạn đã thấy, các giải pháp sẽ không nhất thiết phải tối ưu nhưng dễ thực hiện và có thể đủ tốt. Nếu bạn cần một tốt hơn thì bạn có thể cần phải khám phá nhiều kết hợp hơn và xếp hạng chúng theo số lượng phép nhân bạn tiết kiệm nhưng khái niệm chung là như nhau.