Ottimizzazione di un set di polinomi per la velocità di calcolo

Question

Ho un set di espressioni polinomiali prodotte da un sistema di algebra del computer (CAS). Ad esempio, questo è un elemento di questo set.

-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

Ho bisogno di eseguirli tutti in un programma C, il più velocemente possibile. Se osservi attentamente una di queste formule, è ovvio che possiamo ottimizzarle per la velocità di calcolo. Per esempio, nel polinomio incollato sopra, posso vedere immediatamente i termini -d * d * l * l * q, 2 * d * f * j * l * q, e -f * f * j * j * q, in modo che potessi sostituire la loro somma per -q * quadrato (d * lf * j). Credo che ci siano molte cose che possono essere fatte qui. Non credo (ma forse sbaglio) che qualsiasi compilatore sarebbe in grado di trovare questa ottimizzazione, o forse più avanzata. Ho provato a chiedere a maxima (un CAS) di fare questo per me, ma non è uscito nulla (dato che sono un principiante con maxima, forse ho perso un comando magico). Quindi, la mia prima domanda è: quale strumento/algoritmo possiamo usare per ottimizzare un'espressione polinomiale per la velocità di calcolo?

Quando si tratta di ottimizzare un insieme di espressioni polinomiali che condividono la maggior parte delle loro variabili, le cose diventano più complicate. In effetti, l'ottimizzazione dell'espressione per espressione può essere subottimale perché le parti comuni potrebbero essere identificate dal compilatore prima dell'ottimizzazione, ma non più dopo se questo non viene eseguito nel suo insieme. Quindi, la mia seconda domanda è: quale strumento/algoritmo possiamo usare per ottimizzare un insieme di espressioni polinomiali per la velocità di calcolo?

Con i migliori saluti,

P.S. : questo post condivide alcune somiglianze con "computer algebra soft to minimize the number of operations in a set of polynomials", tuttavia le risposte fornite in quel punto ai programmi CAS invece di dire come possiamo usarle per raggiungere il nostro obiettivo.

Answer 1

Come primo tentativo probabilmente proverei l'approccio avido.

Quindi, utilizzando il tuo primo esempio iniziamo con questo:

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

Ora cercare di trovare il modello più ripetuta nei termini. Questo è q, che per fortuna è presente in tutti loro. Rimuoviamo e che ci lascia con

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

Ora fare la stessa cosa, questa volta si ottiene l e il problema si divide in due sottoproblemi.

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

Ripetere in modo ricorsivo fino a quando non c'è la ripetizione a sinistra e tracciare i tuoi passi indietro si può ricorsivamente ricostruire una versione semplificata dell'espressione:

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

Come si può già vedere, la soluzione non sarà necessariamente ottimale ma è facile da implementare e può essere abbastanza buono. Se hai bisogno di uno migliore, probabilmente devi esplorare più combinazioni e classificarle in base al numero di moltiplicazioni che salvi, ma il concetto generale è lo stesso.