Optimizacion de matriz

[femella]

Hola, mi nombre es Fernando y soy de la universidad del bio-bio, mi problema es
el siguiente:

Resulta que estoy trabajando en un proyecto de Ing. Industrial sobre maquinas
paralelas y meta-raps,(todo esto lo estoy programando en C) y necesito ptimizar
un código, yo se que en su universidad hay gente que se especializa en este
tema. El caso es que estoy ocupando una matriz grande(1800 X 1000 aprox.
dependiendo del problema),y recorriéndolas unas 10000 veces. Por otro lado yo
se que al asignar una matriz de la forma tradicional  int matrix[1800][1600],
no es nada mas que una lista en la memoria y que recorrerla por columna es
ineficiente.
Aqui vien mi problema, necesito que esta matriz sea dinámica y crezca a medida
que crece el problema, probé usando un int **matriz, pero esta solución me
alargo enormemente el tmpo de ejecución, por otro lado una matriz en forma de
lista no me sirve mucho por que en una parte del programa debo dirigirme a un
punto especifico(matrix[800][70]) y recorrerla para encontrar ese punto también
afecta el tmpo.
Bueno, con todos estos antecedentes espero que alguien me pueda ayudar o me den
un mail para contactarme con alguna persona.
Ahhh! si esta no es la lista en que tratan estos temas les expongo mis disculpas

De antemano Gracias

FmC