En diverses aplicacions pràctiques cada vegada és més freqüent la presència de problemes d'optimització que involucren variables que han de prendre valors discrets. Degut a la seva naturalesa combinatòria, els problemes d'optimització discrets presenten en general una complexitat computacional exponencial, i per tant són molt més complicats de resoldre que els problemes continus. La present tesi ha centrat el seu treball en l'estudi i solució al problema de trobar, dins d'una retícula definida prèviament, el punt més proper a un punt donat. Aquest problema es pot originar, entre d'altres múltiples aplicacions pràctiques, en la detecció de senyals en sistemes de comunicacions sense fils MIMO (Multiple Input - Multiple Output).

Els problemes d'optimització discrets no poden abordar-se amb mètodes de convergència ràpida basats en derivades. En lloc d'açò, la solució s'obté mitjançant mètodes com Ramificació i Poda, programació dinàmica i cerques heurístiques. El treball presentat ha consistit, en primer lloc, a realitzar un ampli estudi de l'estat de l'art dels mètodes de Recerca Directa (que són mètodes d'optimització no basats en derivades) i dels mètodes Sphere-Decoding (pertanyents a l'esquema de Ramificació i Poda). En segon lloc, s'ha abordat la paral·lelització d'aquests mètodes adreçada a diferents arquitectures, bé siga arquitectures amb memòria compartida, memòria distribuïda i esquemes híbrids; a més d'explorar, en el cas de la Recerca Directa, variants asíncrones de paral·lelització.

Addicionalment es proposen millores en els propis algoritmes seqüencials. Es van dissenyar i implementar diverses variants de mètodes de Recerca Directa, les quals van tenir bons resultats en la resolució del Problema Invers Additiu de Valors Singulars, doncs van aconseguir convergir i obtenir millor precisió en la solució que els mètodes basats en derivades tipus Newton. D'aquí va sorgir la idea d'aplicar els algorismes dissenyats al problema de mínims quadrats discrets. Els resultats de la Recerca Directa a la descodificació de senyals són encoratjadors, ja que van aconseguir arribar a la generalitat de les experimentacions realitzades la solució òptima emprant temps menors que altres variants conegudes d'algorismes de solució exacta. Per la seua banda, en els mètodes Sphere-Decoding, es realitza una aportació al proposar l'ús de la descomposició de valors singulars (SVD) per obtenir radis que estreten una mica més l'espai de recerca de la solució.

Les rutines assolides, tant seqüencials com paral·leles, presenten la característica de ser portables. Les llibreries estan dissenyades i implementades amb un alt grau d'abstracció i encapsulament de manera que puguin ser utilitzades no només per a solucionar el problema en qüestió, sinó que permeten abordar qualsevol problema d'optimització numèrica amb aquests mètodes.