How to solve a very large overdetermined system numerically?

[dilloncyh]

I am doing a project on image processing and I need to solve the following set of equations:

n_x+n_z*( z(x+1,y)-z(x,y) )=0
n_y+n_z*( z(x+1,y)-z(x,y) )=0
and equations of the boundary (bottom and right side of the image):
n_x+n_z*( z(x,y)-z(x-1,y) )=0
n_y+n_z*( z(x,y)-z(x,y-1) )=0

nx,ny,nz is the components of the surface unit vector which are already determined. The aim is to find the surface profile of a 3D object z(x,y).

Now the problem is that since (x,y) is the coordinates of an image, which has a typical size of say x=300 and y=200, so there are #pixs = 300*200 = 60000 unknowns. I try to rewrite the equations into Mz=b, where z and b are vectors of length #pixs, M is a matrix of size 2*#pixs x #pixs. When I try to solve this system of equations using the method of least square in python, I just get memory error.

So my question is, given that overdetermined system of equations with over ten thousand unknowns, how to solve it efficiently in python or matlab? Are there other ways of rewriting it into matrix form or other methods for solving this equation? I notice the matrix M is very sparse, but I have no idea how to utilize it.

thanks

 

[SteamKing]

I am doing a project on image processing and I need to solve the following set of equations:

n_x+n_z*( z(x+1,y)-z(x,y) )=0
n_y+n_z*( z(x+1,y)-z(x,y) )=0

nx,ny,nz is the components of the surface unit vector which are already determined. The aim is to find the surface profile of a 3D object z(x,y). The equations at the boundary are slightly different but they have the same form.

Now the problem is that since (x,y) is the coordinates of an image, which has a typical size of say x=300 and y=200, so there are #pixs = 300*200 = 60000 unknowns. I try to rewrite the equations into Mz=b, where z and b are vectors of length #pixs, M is a matrix of size 2*#pixs x #pixs. When I try to solve this system of equations using the method of least square in python, I just get memory error.

So my question is, given that overdetermined system of equations with over ten thousand unknowns, how to solve it efficiently in python or matlab? Are there other ways of rewriting it into matrix form or other methods for solving this equation? I notice the matrix M is very sparse, but I have no idea how to utilize it.

thanks

There are several suites of matrix routines specifically designed to handle sparse matrices and to take advantage of their nature.

Some of these routine suites are:

The Yale Sparse Matrix Package

suitesparse

Scipy.sparse

You can google each of these packages, or simple search for "sparse matrix" and find what might suit your needs.