Computació algebraica

En matemàtiques i ciències de la computació, la computació algebraica, també anomenada computació simbòlica, és una disciplina científica que es dedica a l'estudi i desenvolupament d'algorismes i programari per a la manipulació d'expressions matemàtiques i altres objectes matemàtics. Encara que, parlant amb propietat, la computació algebraica hauria de ser una subdisciplina de la computació científica, normalment se les considera disciplines diferents, perquè la computació científica es basa normalment en el càlcul numèric amb aritmètica en coma flotant pels nombres (que per definició esdevenen aproximats), mentre que la computació algebraica posa especial èmfasi en la computació exacta d'expressions que contenen variables a les quals no se'ls dona cap valor concret, sinó que es manipulen com a símbols (d'aquí el nom de computació simbòlica).

Els programaris que realitzen càlculs simbòlics s'anomenen sistemes algebraics computacionals, on el terme sistema es refereix a la complexitat de les aplicacions que el formen, i que com a mínim són: un mètode per representar dades matemàtiques en un ordinador, un llenguatge de programació per l'usuari (que normalment és diferent del llenguatge emprat per a la implementació del sistema), un gestor de memòria dedicat, una interfície d'usuari per a l'entrada i la sortida d'expressions matemàtiques, un conjunt ampli de subrutines per realitzar les operacions usuals, com simplificació d'expressions, derivades que usen la regla de la cadena, factorització de polinomis, integració indefinida, etc.

En els inicis de la computació algebraica, vers 1970, quan es van aplicar els algorismes coneguts als ordinadors, es va veure que eren altament ineficients. Per tant, una gran part de la feina dels investigadors consistí a revisar l'àlgebra clàssica per tal de fer-la més efectiva i per descobrir algorismes eficients per tal d'implementar aquesta eficiència. Un exemple típic n'és el càlcul del màxim comú divisor per polinomis, que és necessari per simplificar fraccions.

La computació algebraica s'usa a bastament per dissenyar les fórmules utilitzades en programes numèrics. També s'usa en càlculs científics complets, quan fallen els mètodes purament numèrics, com ara la criptografia de clau pública o alguns problemes no lineals.

Terminologia

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

Comunitat científica

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

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.

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

Aspectes en ciències de la computació

Representació de dades

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.

Nombres

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.

Expressions

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

Simplificació

Una expressió com

${\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 ${\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 $(x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1$ i $(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).

Consideracions matemàtiques

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, $(\sin(x+y)^{2}+\log(z^{2}-5))^{3}$ es pot veure com un polinomi en $\sin(x+y)$ i $\log(z^{2}-5)$.

Igualtat

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

Bibliografia

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.