Hola Pedro, buen análisis. Habría que ver como implementaste el código y si esta solución se puede aplicar a las demás matrices. Para optimizar el código te sugiero implementar el método SOR indicialmente y trabajar con las matrices fila por fila:
Como marcaste en cada fila las matrices tienen muchisimos 0, entonces en las dos sumatorias adentro del paréntesis cada vez que toque un a_ij nulo no va a sumar nada, pero igual va a estar haciendo la operación. Esto sería lo mismo que directamente aplicar la sumatoria filtrando los aij que son 0. En Python tenes una función que te devuelve los índices no nulos de la matriz o vector que le pongas (np.nonzeros())