Hi all, hope this is the right place for this kind of request.
I'm writing a program which will be doing Machine Learning over graph data structures. In it I'm going to be needing to represent a bunch of matrices, some sparse, some definitely not sparse, and do fairly basic operations on these matrices (add/ subtract/multiply, pseudoinverse, probably some others). I've started a basic prototype using the standard CL arrays but I always knew I would need GSLL to calculate a pseudo inverse.
My question is, would it be a reasonably sensible decision to just use marrays for the whole program rather than worrying about converting to/ from CL-type arrays all the time? Are there any places where CL-arrays beat marrays either in terms of memory usage, access speed, or anything else? I might be needing to scale this system up be dealing with N*N square matrices where N is on the order of hundreds of thousands or even millions, if that makes any difference to the recommendation.
Thanks in advance for any help!
Malcolm Reynolds
Yes, it is definitely my recommendation to use marrays everywhere. I am starting to get in the habit of doing so myself. One of my ideas is to extend CL array operations to marrays so that you need not convert back and forth. It is also my intent that other math software libraries would also use marrays (or an extension of them), so that they become a standard way to interchange data between libraries.
There is more overhead for marrays than plain arrays, but on SBCL where the native arrays are used in GSL directly, there is very little, and there is no copying. I recommend that you build it with marray and then see if you have performance problems. However, if you are talking matrices of 1000000x1000000, I think you will have problems in any representation on almost any kind of hardware. For single floats, one such matrix is 4TB. In that case, I recommend you rethink the problem structure. If these are sparse matrices, you should use a sparse matrix representation. GSL doesn't have such a representation, but others have been interested in having it so it might be worth posting something to the GSL mailing list -- perhaps someone has written a GSL-compatible sparse array representation.
Liam
On Sat, Apr 11, 2009 at 8:12 AM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi all, hope this is the right place for this kind of request.
I'm writing a program which will be doing Machine Learning over graph data structures. In it I'm going to be needing to represent a bunch of matrices, some sparse, some definitely not sparse, and do fairly basic operations on these matrices (add/ subtract/multiply, pseudoinverse, probably some others). I've started a basic prototype using the standard CL arrays but I always knew I would need GSLL to calculate a pseudo inverse.
My question is, would it be a reasonably sensible decision to just use marrays for the whole program rather than worrying about converting to/ from CL-type arrays all the time? Are there any places where CL-arrays beat marrays either in terms of memory usage, access speed, or anything else? I might be needing to scale this system up be dealing with N*N square matrices where N is on the order of hundreds of thousands or even millions, if that makes any difference to the recommendation.
Thanks in advance for any help!
Malcolm Reynolds
Gsll-devel mailing list Gsll-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
Hi Liam, thanks for your response.
Glad to hear that marrays are recommended, and especially that they are implemented well on SBCL as that is what I'm using.
As for the million element square matrices then yes, clearly on reflection that won't work. Some of the matrices I'm using will be sparse, but some will not be sparse at all - without wanting to get bogged down in details, I'm going to need to represent the Graph Laplacian, which is a matrix that is equal to the degree matrix minus the adjacency matrix (and so in a fairly sparse graph this matrix is sparse) but I will also need the graph Kernel, which is the pseudoinverse of the Laplacian. This will not be sparse at all, so clearly a direct representation of it isn't possible. I know of someone in my university's department who has a fast method for this kind of situation which means that calculating the full kernel matrix is unnecessary, so I guess I can look into that if and when I find that performance is a limiting factor.
Anyway thanks again for your response, and for your hard work on GSLL. I'm pretty new to lisp and I'm continuously impressed by the quality of the libraries!
Malcolm
On Sat, Apr 11, 2009 at 3:46 PM, Liam Healy lhealy@common-lisp.net wrote:
Yes, it is definitely my recommendation to use marrays everywhere. I am starting to get in the habit of doing so myself. One of my ideas is to extend CL array operations to marrays so that you need not convert back and forth. It is also my intent that other math software libraries would also use marrays (or an extension of them), so that they become a standard way to interchange data between libraries.
There is more overhead for marrays than plain arrays, but on SBCL where the native arrays are used in GSL directly, there is very little, and there is no copying. I recommend that you build it with marray and then see if you have performance problems. However, if you are talking matrices of 1000000x1000000, I think you will have problems in any representation on almost any kind of hardware. For single floats, one such matrix is 4TB. In that case, I recommend you rethink the problem structure. If these are sparse matrices, you should use a sparse matrix representation. GSL doesn't have such a representation, but others have been interested in having it so it might be worth posting something to the GSL mailing list -- perhaps someone has written a GSL-compatible sparse array representation.
Liam
On Sat, Apr 11, 2009 at 8:12 AM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi all, hope this is the right place for this kind of request.
I'm writing a program which will be doing Machine Learning over graph data structures. In it I'm going to be needing to represent a bunch of matrices, some sparse, some definitely not sparse, and do fairly basic operations on these matrices (add/ subtract/multiply, pseudoinverse, probably some others). I've started a basic prototype using the standard CL arrays but I always knew I would need GSLL to calculate a pseudo inverse.
My question is, would it be a reasonably sensible decision to just use marrays for the whole program rather than worrying about converting to/ from CL-type arrays all the time? Are there any places where CL-arrays beat marrays either in terms of memory usage, access speed, or anything else? I might be needing to scale this system up be dealing with N*N square matrices where N is on the order of hundreds of thousands or even millions, if that makes any difference to the recommendation.
Thanks in advance for any help!
Malcolm Reynolds
Gsll-devel mailing list Gsll-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
On a related point, I'm writing some unit tests using your modified version of lisp-unit (the one from repo.or.cz) and I haven't as yet been able to figure out a good way to compare two matrices for equality. In the automatically generated tests in the GSLL code it appears you do (cl-array ...) to convert the matrices back to native form. Is this the best way possible, or is there some numerical equality predicate in the gsll library that I've missed? It would seem to be ideal to be able to define a test by (assert-numerical-equal <marray 1> <marray 2>) but I get an error message when I try this...
Malcolm
On Mon, Apr 13, 2009 at 2:24 PM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi Liam, thanks for your response.
Glad to hear that marrays are recommended, and especially that they are implemented well on SBCL as that is what I'm using.
As for the million element square matrices then yes, clearly on reflection that won't work. Some of the matrices I'm using will be sparse, but some will not be sparse at all - without wanting to get bogged down in details, I'm going to need to represent the Graph Laplacian, which is a matrix that is equal to the degree matrix minus the adjacency matrix (and so in a fairly sparse graph this matrix is sparse) but I will also need the graph Kernel, which is the pseudoinverse of the Laplacian. This will not be sparse at all, so clearly a direct representation of it isn't possible. I know of someone in my university's department who has a fast method for this kind of situation which means that calculating the full kernel matrix is unnecessary, so I guess I can look into that if and when I find that performance is a limiting factor.
Anyway thanks again for your response, and for your hard work on GSLL. I'm pretty new to lisp and I'm continuously impressed by the quality of the libraries!
Malcolm
On Sat, Apr 11, 2009 at 3:46 PM, Liam Healy lhealy@common-lisp.net wrote:
Yes, it is definitely my recommendation to use marrays everywhere. I am starting to get in the habit of doing so myself. One of my ideas is to extend CL array operations to marrays so that you need not convert back and forth. It is also my intent that other math software libraries would also use marrays (or an extension of them), so that they become a standard way to interchange data between libraries.
There is more overhead for marrays than plain arrays, but on SBCL where the native arrays are used in GSL directly, there is very little, and there is no copying. I recommend that you build it with marray and then see if you have performance problems. However, if you are talking matrices of 1000000x1000000, I think you will have problems in any representation on almost any kind of hardware. For single floats, one such matrix is 4TB. In that case, I recommend you rethink the problem structure. If these are sparse matrices, you should use a sparse matrix representation. GSL doesn't have such a representation, but others have been interested in having it so it might be worth posting something to the GSL mailing list -- perhaps someone has written a GSL-compatible sparse array representation.
Liam
On Sat, Apr 11, 2009 at 8:12 AM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi all, hope this is the right place for this kind of request.
I'm writing a program which will be doing Machine Learning over graph data structures. In it I'm going to be needing to represent a bunch of matrices, some sparse, some definitely not sparse, and do fairly basic operations on these matrices (add/ subtract/multiply, pseudoinverse, probably some others). I've started a basic prototype using the standard CL arrays but I always knew I would need GSLL to calculate a pseudo inverse.
My question is, would it be a reasonably sensible decision to just use marrays for the whole program rather than worrying about converting to/ from CL-type arrays all the time? Are there any places where CL-arrays beat marrays either in terms of memory usage, access speed, or anything else? I might be needing to scale this system up be dealing with N*N square matrices where N is on the order of hundreds of thousands or even millions, if that makes any difference to the recommendation.
Thanks in advance for any help!
Malcolm Reynolds
Gsll-devel mailing list Gsll-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel
I haven't defined such a predicate, but I think it's a good idea. As you have seen, in order to do tests on marrays, I turn all the marrays into CL arrays and do the comparisons on the result. I don't know if it's the best possible way to do it, but it works. You get an error from assert-numerical-equal because it uses #'numerical-equal as a test, and that does not handle marrays. Your suggestion spurred me to take a look at the lisp-unit source; what I'm thinking about is changing #'numerical-equal to a generic function with some methods pre-defined for CL classes; this would permit applications like GSLL to add methods for their own objects.
I've cc'ed Tom Hermann on this email; he is behind the modified version of lisp-unit more so than I am. Tom: what do you think of this idea?
Liam
On Mon, Apr 13, 2009 at 11:05 AM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
On a related point, I'm writing some unit tests using your modified version of lisp-unit (the one from repo.or.cz) and I haven't as yet been able to figure out a good way to compare two matrices for equality. In the automatically generated tests in the GSLL code it appears you do (cl-array ...) to convert the matrices back to native form. Is this the best way possible, or is there some numerical equality predicate in the gsll library that I've missed? It would seem to be ideal to be able to define a test by (assert-numerical-equal <marray 1> <marray 2>) but I get an error message when I try this...
Malcolm
On Mon, Apr 13, 2009 at 2:24 PM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi Liam, thanks for your response.
Glad to hear that marrays are recommended, and especially that they are implemented well on SBCL as that is what I'm using.
As for the million element square matrices then yes, clearly on reflection that won't work. Some of the matrices I'm using will be sparse, but some will not be sparse at all - without wanting to get bogged down in details, I'm going to need to represent the Graph Laplacian, which is a matrix that is equal to the degree matrix minus the adjacency matrix (and so in a fairly sparse graph this matrix is sparse) but I will also need the graph Kernel, which is the pseudoinverse of the Laplacian. This will not be sparse at all, so clearly a direct representation of it isn't possible. I know of someone in my university's department who has a fast method for this kind of situation which means that calculating the full kernel matrix is unnecessary, so I guess I can look into that if and when I find that performance is a limiting factor.
Anyway thanks again for your response, and for your hard work on GSLL. I'm pretty new to lisp and I'm continuously impressed by the quality of the libraries!
Malcolm
On Sat, Apr 11, 2009 at 3:46 PM, Liam Healy lhealy@common-lisp.net wrote:
Yes, it is definitely my recommendation to use marrays everywhere. I am starting to get in the habit of doing so myself. One of my ideas is to extend CL array operations to marrays so that you need not convert back and forth. It is also my intent that other math software libraries would also use marrays (or an extension of them), so that they become a standard way to interchange data between libraries.
There is more overhead for marrays than plain arrays, but on SBCL where the native arrays are used in GSL directly, there is very little, and there is no copying. I recommend that you build it with marray and then see if you have performance problems. However, if you are talking matrices of 1000000x1000000, I think you will have problems in any representation on almost any kind of hardware. For single floats, one such matrix is 4TB. In that case, I recommend you rethink the problem structure. If these are sparse matrices, you should use a sparse matrix representation. GSL doesn't have such a representation, but others have been interested in having it so it might be worth posting something to the GSL mailing list -- perhaps someone has written a GSL-compatible sparse array representation.
Liam
On Sat, Apr 11, 2009 at 8:12 AM, Malcolm Reynolds malcolm.reynolds@gmail.com wrote:
Hi all, hope this is the right place for this kind of request.
I'm writing a program which will be doing Machine Learning over graph data structures. In it I'm going to be needing to represent a bunch of matrices, some sparse, some definitely not sparse, and do fairly basic operations on these matrices (add/ subtract/multiply, pseudoinverse, probably some others). I've started a basic prototype using the standard CL arrays but I always knew I would need GSLL to calculate a pseudo inverse.
My question is, would it be a reasonably sensible decision to just use marrays for the whole program rather than worrying about converting to/ from CL-type arrays all the time? Are there any places where CL-arrays beat marrays either in terms of memory usage, access speed, or anything else? I might be needing to scale this system up be dealing with N*N square matrices where N is on the order of hundreds of thousands or even millions, if that makes any difference to the recommendation.
Thanks in advance for any help!
Malcolm Reynolds
-
Liam Healy -
Malcolm Reynolds