Computació algebraica

Alguns autors distingeixen entre àlgebra computacional i computació simbòlica, i empren aquest darrer terme per referir-se a altres tipus de computació simbòlica diferents de la computació amb fórmules matemàtiques. Alguns autors empren computació simbòlica per denominar la ciència de la computació referida a aquest tema, i "àlgebra computacional" per l'aspecte matemàtic.^[2] En alguns idiomes, aquest terme no és una traducció literal; per exemple, en francès s'anomena calcul formel, que significa "càlcul formal".

En el passat, la computació simbòlica s'ha denominat com manipulació simbòlica, manipulació algebraica, processament simbòlic, matemàtica simbòlica o àlgebra simbòlica, però aquests termes han caigut en desús per referir-se a la computació simbòlica, ja que denominen aspectes de manipulació no computacional.

No hi ha cap societat científica que es dediqui específicament a la computació algebraica, però aquesta funció està assumida per l'special interest group de l'Association for Computing Machinery anomenat SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation; en anglès, Grup d'Interès Especial per la Manipulació Algebraica i Simbòlica).^[3]

Existeixen diverses conferències anuals sobre computació algebraica, la més important d'elles ISSAC (International Symposium on Symbolic and Algebraic Computation; en anglès, Simposi Internacional sobre Computació Simbòlica i Algebraica), impulsada per SIGSAM.^[4]

També existeixen diverses publicacions especialitzades en computació algebraica, la més important el Journal of Symbolic Computation fundada el 1985 per Bruno Buchberger.^[5] Altres publicacions publiquen de forma regular articles sobre computació algebraica.^[6]

Com que els programaris de càlcul numèric són altament eficients per realitzar càlculs aproximats, és força comú, en computació algebraica, posar èmfasi en realitzar càlculs exactes amb dades representades de forma exacta. Aquesta representació tan exacta implica que, encara que la grandària de la sortida sigui petita, les dades intermèdies generades durant un càlcul poden créixer d'una forma impredictible. Aquest comportament s'anomena inflor de l'expressió (en anglès, expression swell). Per esmenar aquest problema, hom usa diversos mètodes en la representació de les dades, així com en els algorismes que les manipulen.

Els sistemes numèrics habituals emprats en anàlisi numèrica són o bé la representació de nombres en coma flotant o els enters d'una grandària màxima fixada, que s'anomenen de forma impròpia enters per la majoria de llenguatges de programació. Cap d'ells és convenient per la computació algebraica, a causa de l'efecte d'inflor de l'expressió.

En lloc d'això, els nombres bàsics emprats en computació algebraica són els enters matemàtics, normalment representats com una seqüència de dígits en alguna base de numeració, normalment la major base permesa per la paraula de la màquina. Aquests enters permeten definir els nombres racionals, que són fraccions irreduïbles de dos enters.

El procés de programar una implementació eficient de les operacions aritmètiques és una tasca difícil. Per tant, la majoria de sistemes algebraics computacionals i alguns de comercials, com Maple, usen la llibreria GMP, que ha esdevingut un estàndard de facto.

Excepte per nombres i variables, tota expressió matemàtica es pot veure com el símbol d'un operador seguit d'una seqüència d'operands.^[7] En programaris de computació algebraica, les expressions s'acostumen a representar d'aquesta manera. Aquesta representació és molt flexible, i molts termes que no semblen una expressió matemàtica a primer cop d'ull, es poden representar i manipular com a tals. Per exemple, una equació és una expressió on l'operador és "=", una matriu es pot representar com una expressió amb l'operador "matriu" i on les files i les columnes en són els operands.

Fins i tot els programes es poden considerar i representar com a expressions, amb l'operador "procediment" i, almenys, dos operands, la llista de paràmetres i el cos, que és al seu torn una expressió amb l'operador "cos" i una seqüència d'instruccions com a operands. Recíprocament, qualsevol expressió matemàtica es pot veure com un programa. Per exemple, l'expressió a+b es pot veure com un programa per l'addició, on a i b en són els paràmetres. Executar aquest programa consisteix a avaluar l'expressió per valors donats de a i b; si no tenen cap valor (és a dir, són indeterminats), el resultat de l'avaluació és simplement l'entrada.

El procés d'avaluació diferida és fonamental en computació algebraica. Per exemple, l'operador "=" de les equacions també és, en la majoria de sistemes algebraics computacionals, el nom del programa per la prova d'igualtat: normalment, l'avaluació d'una equació resulta en una equació; però, quan es necessita una prova d'igualtat, llavors l'avaluació retorna un 0 o un 1 booleans.

Com que la grandària dels operands d'una expressió és impredictible i pot canviar durant una sessió de treball, la seqüència d'operands se sol representar com una seqüència de punters (com en Macsyma) o com a entrades d'una taula hash (com en Maple).

Una expressió com

${\displaystyle {\frac {1}{4(x-1)}}-{\frac {1}{4(x+1)}}-{\frac {1}{2(x^{2}+1)}}}$ 

és farragosa i difícil de manipular. Per tal de simplificar-la a ${\displaystyle {\frac {1}{x^{4}-1}}}$  és necessari proveir-se de regles de simplificació per a aquesta i d'altres expressions.

Aquesta simplificació es du a terme normalment mitjançant regles de reescriptura. Existeixen diferents tipus de regles de reescriptura; n'és un exemple la intenció de reduir la grandària de l'expressió, com ara sin(0) → 0. Aquestes regles s'apliquen de forma sistemàtica en els sistemes algebraics computacionals.

La primera dificultat apareix amb les operacions associatives com l'addició i la multiplicació. La forma habitual de tractar l'associativitat és considerar que la suma i la multiplicació tenen un nombre arbitrari d'operands, és a dir, a+b+c es representa com "+"(a, b, c). Quant a la subtracció i la divisió, la forma més senzilla és reescriure -E, E-F, E/F com a (-1)·E, E + (-1)·F, E·F⁻¹, respectivament. En altres paraules, en la representació interna de les expressions, no hi ha cap substracció ni divisió ni oposat per la suma, llevat de la representació dels nombres.

Apareix una segona dificultat amb la commutativitat de l'addició i de la multiplicació. El problema rau en reconèixer ràpidament els termes semblants per tal de combinar-los o cancel·lar-los. De fet, el mètode per trobar els termes semblants, consistent en provar cada parell de termes, és massa costós per fer-lo practicable amb sumes o productes molt llargs. Per resoldre aquest problema, Macsyma ordena els operands de sumes i productes mitjançant una funció de comparació que situa els termes semblants en posicions consecutives, i així es poden detectar fàcilment. En Maple, la funció de hash està dissenyada per generar col·lisions quan es troben termes semblants, i això permet combinar-los a mesura que s'introdueixen. Aquest disseny de la funció de hash també permet reconèixer de forma immediata les expressions de subexpressions que apareixen diversos cops en un càlcul, i emmagatzemar-los una sola vegada. Això comporta no només un estalvi d'espai, sinó també una acceleració dels càlculs, perquè així s'evita repetir el mateix càlcul en diverses expressions idèntiques.

Algunes regles de reescriptura de vegades incrementen i de vegades disminueixen la grandària de les expressions a les quals s'apliquen. Aquest és el cas de la distributivitat o les identitats trigonomètriques. Per exemple, la propietat distributiva permet reescriure ${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$  i ${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$  Com que, en general, no es pot predir si una regla de reescriptura portarà a una expressió més senzilla o més complicada, normalment s'apliquen aquestes regles només quan l'usuari ho demana explícitament. En el cas de la distributivitat, la funció que aplica aquesta regla s'acostuma a anomenar "expansió". La regla de reescriptura inversa, anomenada "factorització", requereix un algorisme no trivial, i per tant esdevé una funció clau en els sistemes algebraics computacionals (vegeu Factorització dels polinomis).

En aquesta secció considerem algunes qüestions matemàtiques fonamentals que sorgeixen tan bon punt es manipulen expressions mitjançant un ordinador. Considerem principalment el cas de les fraccions algebraiques en diverses variables. De fet, això no és una restricció perquè, a mesura que hom es troba amb funcions irracionals en el procés de simplificació d'una expressió, hom les considera com a noves incògnites. Per exemple, ${\displaystyle (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$  es pot veure com un polinomi en ${\displaystyle \sin(x+y)}$  i ${\displaystyle \log(z^{2}-5)}$ .

Hi ha dues nocions d'igualtat per les expressions matemàtiques. La igualtat sintàctica és la igualtat de les expressions en si, la qual cosa vol dir que s'escriuen (o es representen en un ordinador) de la mateixa manera. Com que verificar això és trivial, rarament té importància matemàtica, però és l'única igualtat que es pot comprovar fàcilment amb un ordinador. La igualtat semàntica es dona quan dues expressions diferents representen el mateix objecte matemàtic, com per exemple ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$ 

És conegut que pot no existir un algorisme que decideixi si dues expressions són semànticament iguals, si es permet l'ús de logaritmes i exponencials. Per tant, la igualtat (semàntica) només es pot verificar en algunes classes d'expressions, com ara els polinomis o les fraccions racionals.

Per tal de verificar la igualtat de dues expressions, en comptes de dissenyar un algorisme específic, normalment es transformen les expressions en alguna forma canònica, o bé es reescriu la seva diferència en una forma normal, i llavors es verifica la igualtat sintàcica del resultat.

Contràriament al que succeeix en les matemàtiques en general, "forma canònica" i "forma normal" no són sinònims en computació algebraica. Dues formes canóniques de dues expressions són semànticament iguals si i només si són sintàcticament iguals. D'altra banda, una expressió en forma normal és semànticament zero només si és sintàcticament zero. En altres paraules, el zero té una única representació per expressions en forma normal.

Habitualment, hom prefereix les formes normals a les formes canòniques en l'àmbit de la computació algebraica. D'una banda, les formes canòniques poden ser més costoses de calcular que les formes normals. Per exemple, per reescriure un polinomi en forma canònica, s'ha de expandir cada producte mitjançant la distributivitat, mentre que això no és necessari per a calcular la forma normal. Addicionalment, pot ser (per exemple en expressions amb radicals) que una forma canònica, si existeix, depengui d'algunes eleccions arbitràries, i aquestes eleccions poden variar per dues expressions que han estat calculades de forma independent. Aquest és un motiu perquè l'ús d'una forma canònica sigui impracticable.

 

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Computació algebraica

Per a una definició detallada:

• Buchberger, Bruno. «Symbolic Computation (an editorial)» (pdf). Journal of Symbolic Computation p. 1-6, 1985. Arxivat de l'original el 24 de setembre 2015. [Consulta: 24 setembre 2013].

Per a obres sobre el tema:

• Davenport, James H.; Siret, Y.; Davenport, E. Tournier; translated from the French by A.; Davenport, J.H.. Computer algebra : systems and algorithms for algebraic computation. 2. print.. Londres: Academic Press, 1988. ISBN 978-0-12-204230-0. 
• Gerhard, Joachim von Zur Gathen; Jürgen. Modern computer algebra. 2. ed.. Cambridge [u.a.]: Cambridge Univ. Press, 2003. ISBN 0-521-82646-2. 
• Labahn, K.O. Geddes; S.R. Czapor; G.. Algorithms for computer algebra. 6. pr.. Boston [u.a.]: Kluwer, 1999. ISBN 978-0-7923-9259-0. 
• Buchberger, Bruno. Computer algebra : symbolic and algebraic computation. 2. ed.. Wien [u.a.]: Springer, 1983. ISBN 978-3-211-81776-6.