Re: [sqlite] sparse matrix in scientific computing with sqlite
Michael Chen wrote: > --this is my first version for the purpose of storing sparse numerical > matrix in sql > --please let me know how to fix the bug at the end of the file, and how to > tune the performance > --or any better reference, thanks! > > .explain-- return result in more readable > format > .echo on-- echo the sql stmnt > > --I plan to store my sparse matrix (3 x 4) in table like this: > -- [ 1 2 0 0 ] > -- [ 0 3 9 0 ] > -- [ 0 1 4 0 ] > A sparse matrix can be stored in a table like CREATE TABLE Matrix ( Row INTEGER NOT NULL, Col INTEGER NOT NULL, Value REAL, PRIMARY KEY (Row, Col) ); With this representation, arithmetic on matrices can be done as: -- MatrixA + MatrixB SELECT Row, Col, SUM(Value) AS Value FROM (SELECT * FROM MatrixA UNION ALL SELECT * FROM MatrixB) GROUP BY Row, Col; -- MatrixA - MatrixB SELECT Row, Col, SUM(Value) AS Value FROM (SELECT * FROM MatrixA UNION ALL SELECT Row, Col, -Value FROM MatrixB) GROUP BY Row, Col; -- MatrixA * MatrixB SELECT MatrixA.Row AS Row, MatrixB.Col AS Col, SUM(MatrixA.Value * MatrixB.Value) AS Value FROM MatrixA INNER JOIN MatrixB ON MatrixA.Col = MatrixB.Row GROUP BY Row, Col; ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] sparse matrix in scientific computing with sqlite
yes, that's what I am thinking of too. This big table is in charge of store all matrix, keep track of all index changes, and rollback when needed. I will only extract a tiny part from this big table in format like a sparse matrix, and put it in C array, then the available numerical routines, such as matrix inversion, can be applied to the C array. So this big table for all matrix is a information manager or a data warehouse in my thinking. I am not sure how easy it will be to use this big table as a central warehouse for now. On Fri, Oct 16, 2009 at 3:50 PM, Stephan Wehner wrote: > On Fri, Oct 16, 2009 at 1:41 PM, Michael Chen > wrote: > > rdbms is indeed not a place for store a single sparse matrix like this. > > However I have hundreds of them, and I need to break them and recombine > them > > frequently; furthermore, I need to drop a few rows or columns > successively, > > and need to be able to trace back what's a row's original index. I think > > sqlite in my C/C++ code will save lots of boring reindexing coding, and > it > > is more robust. > > Would you not store all the matrices in one table, and use a > "matrix_id" column to identify which records are for one matrix ? > > Stephan > > > > > On Fri, Oct 16, 2009 at 1:14 PM, P Kishor wrote: > > > >> This is not the answer you are looking for, and there are SQL geniuses > >> on this list who will help you better, but really, is an rdbms really > >> a good place to store a matrix the way you are trying to do? So > >> convoluted. > >> > >> My approach, if I really was determined to store it in sqlite, would > >> be to flatten the matrix in my code, and then stuff that into a table. > >> Retrieve it and deserialize it as needed. For example, Perl's freeze, > >> thaw are tailor made for this kind of stuff. > >> > >> > >> On Fri, Oct 16, 2009 at 1:09 PM, Michael Chen > >> wrote: > >> > --this is my first version for the purpose of storing sparse numerical > >> > matrix in sql > >> > --please let me know how to fix the bug at the end of the file, and > how > >> to > >> > tune the performance > >> > --or any better reference, thanks! > >> > > >> > .explain-- return result in more > readable > >> > format > >> > .echo on-- echo the sql stmnt > >> > > >> > --I plan to store my sparse matrix (3 x 4) in table like this: > >> > -- [ 1 2 0 0 ] > >> > -- [ 0 3 9 0 ] > >> > -- [ 0 1 4 0 ] > >> > -- > >> > -- is a three-by-four matrix with six nonzero elements, so > >> > -- > >> > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order > >> > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero > element > >> of > >> > row i in A > >> > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero > >> element > >> > A(i) > >> > -- > >> > -- Note: In this example, the row and line index begin by 1 and not 0. > >> > > >> > create table rowids( > >> > rows integer primary key -- there should be an easy way for a > sequence > >> > 1..M? > >> > ); > >> > > >> > insert into rowids values (1); > >> > insert into rowids values (2); > >> > insert into rowids values (3); > >> > > >> > create table colids( > >> > cols integer primary key -- there should be an easy way for a > sequence > >> > 1..N? > >> > ); > >> > > >> > insert into colids values (1); > >> > insert into colids values (2); > >> > insert into colids values (3); > >> > insert into colids values (4); > >> > > >> > > >> > create table matrix( > >> > rowid integer reference rowids, > >> > colid integer reference colids, > >> > value real non null > >> > ); > >> > > >> > insert into matrix values (1,1,1); > >> > insert into matrix values (1,2,2); > >> > insert into matrix values (2,2,3); > >> > insert into matrix values (2,3,9); > >> > insert into matrix values (3,2,1); > >> > insert into matrix values (3,3,4); > >> > insert into matrix values (2,4,0); --this entry is inserted on purpose > >> > > >> > > >> > select * from matrix; > >> > > >> > > >> > --A rowwise sparse matrix is then: > >> > > >> > create temp view rowwiseA as > >> > select value as A, colid as JA from matrix > >> > where value != 0 > >> > order by rowid, colid > >> > ; > >> > > >> > create temp view rowwiseB as > >> > select rowid, count(rowid) as ct > >> > from matrix > >> > where value != 0 > >> > group by rowid > >> > order by rowid > >> > ; > >> > > >> > create temp view rowwiseC as > >> > select a1.rowid, sum(a2.ct) +1 as JA > >> > from rowwiseB a1, rowwiseB a2 > >> > where a2.rowid < a1.rowid > >> > group by a1.rowid > >> > ; > >> > --this is not quite right yet, the first entry and last entry of JA > >> vector > >> > is not here. > >> > > >> > select * from rowwiseA; > >> > select * from rowwiseB; > >> > select * from rowwiseC; > >> > > >> > > >> > create temp view rowwiseB as > >> > select count(rowid) as ia from matrix > >> > where value != 0 > >> > group by rowid > >> > order by rowid > >> > ; > >> > > >> > > >> > > >> > --Best regards
Re: [sqlite] sparse matrix in scientific computing with sqlite
On Fri, Oct 16, 2009 at 1:41 PM, Michael Chen wrote: > rdbms is indeed not a place for store a single sparse matrix like this. > However I have hundreds of them, and I need to break them and recombine them > frequently; furthermore, I need to drop a few rows or columns successively, > and need to be able to trace back what's a row's original index. I think > sqlite in my C/C++ code will save lots of boring reindexing coding, and it > is more robust. Would you not store all the matrices in one table, and use a "matrix_id" column to identify which records are for one matrix ? Stephan > > On Fri, Oct 16, 2009 at 1:14 PM, P Kishor wrote: > >> This is not the answer you are looking for, and there are SQL geniuses >> on this list who will help you better, but really, is an rdbms really >> a good place to store a matrix the way you are trying to do? So >> convoluted. >> >> My approach, if I really was determined to store it in sqlite, would >> be to flatten the matrix in my code, and then stuff that into a table. >> Retrieve it and deserialize it as needed. For example, Perl's freeze, >> thaw are tailor made for this kind of stuff. >> >> >> On Fri, Oct 16, 2009 at 1:09 PM, Michael Chen >> wrote: >> > --this is my first version for the purpose of storing sparse numerical >> > matrix in sql >> > --please let me know how to fix the bug at the end of the file, and how >> to >> > tune the performance >> > --or any better reference, thanks! >> > >> > .explain -- return result in more readable >> > format >> > .echo on -- echo the sql stmnt >> > >> > --I plan to store my sparse matrix (3 x 4) in table like this: >> > -- [ 1 2 0 0 ] >> > -- [ 0 3 9 0 ] >> > -- [ 0 1 4 0 ] >> > -- >> > -- is a three-by-four matrix with six nonzero elements, so >> > -- >> > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order >> > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element >> of >> > row i in A >> > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero >> element >> > A(i) >> > -- >> > -- Note: In this example, the row and line index begin by 1 and not 0. >> > >> > create table rowids( >> > rows integer primary key -- there should be an easy way for a sequence >> > 1..M? >> > ); >> > >> > insert into rowids values (1); >> > insert into rowids values (2); >> > insert into rowids values (3); >> > >> > create table colids( >> > cols integer primary key -- there should be an easy way for a sequence >> > 1..N? >> > ); >> > >> > insert into colids values (1); >> > insert into colids values (2); >> > insert into colids values (3); >> > insert into colids values (4); >> > >> > >> > create table matrix( >> > rowid integer reference rowids, >> > colid integer reference colids, >> > value real non null >> > ); >> > >> > insert into matrix values (1,1,1); >> > insert into matrix values (1,2,2); >> > insert into matrix values (2,2,3); >> > insert into matrix values (2,3,9); >> > insert into matrix values (3,2,1); >> > insert into matrix values (3,3,4); >> > insert into matrix values (2,4,0); --this entry is inserted on purpose >> > >> > >> > select * from matrix; >> > >> > >> > --A rowwise sparse matrix is then: >> > >> > create temp view rowwiseA as >> > select value as A, colid as JA from matrix >> > where value != 0 >> > order by rowid, colid >> > ; >> > >> > create temp view rowwiseB as >> > select rowid, count(rowid) as ct >> > from matrix >> > where value != 0 >> > group by rowid >> > order by rowid >> > ; >> > >> > create temp view rowwiseC as >> > select a1.rowid, sum(a2.ct) +1 as JA >> > from rowwiseB a1, rowwiseB a2 >> > where a2.rowid < a1.rowid >> > group by a1.rowid >> > ; >> > --this is not quite right yet, the first entry and last entry of JA >> vector >> > is not here. >> > >> > select * from rowwiseA; >> > select * from rowwiseB; >> > select * from rowwiseC; >> > >> > >> > create temp view rowwiseB as >> > select count(rowid) as ia from matrix >> > where value != 0 >> > group by rowid >> > order by rowid >> > ; >> > >> > >> > >> > --Best regards, >> > --Michael Chen >> > --Google Voice Phone.: 847-448-0647 >> > ___ >> > sqlite-users mailing list >> > sqlite-users@sqlite.org >> > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users >> > >> >> >> >> -- >> Puneet Kishor http://www.punkish.org >> Carbon Model http://carbonmodel.org >> Charter Member, Open Source Geospatial Foundation http://www.osgeo.org >> Science Commons Fellow, http://sciencecommons.org/about/whoweare/kishor >> Nelson Institute, UW-Madison http://www.nelson.wisc.edu >> --- >> Assertions are politics; backing up assertions with evidence is science >> === >> Sent from Madison, WI, United States >> ___ >> sqlite-us
Re: [sqlite] sparse matrix in scientific computing with sqlite
rdbms is indeed not a place for store a single sparse matrix like this. However I have hundreds of them, and I need to break them and recombine them frequently; furthermore, I need to drop a few rows or columns successively, and need to be able to trace back what's a row's original index. I think sqlite in my C/C++ code will save lots of boring reindexing coding, and it is more robust. On Fri, Oct 16, 2009 at 1:14 PM, P Kishor wrote: > This is not the answer you are looking for, and there are SQL geniuses > on this list who will help you better, but really, is an rdbms really > a good place to store a matrix the way you are trying to do? So > convoluted. > > My approach, if I really was determined to store it in sqlite, would > be to flatten the matrix in my code, and then stuff that into a table. > Retrieve it and deserialize it as needed. For example, Perl's freeze, > thaw are tailor made for this kind of stuff. > > > On Fri, Oct 16, 2009 at 1:09 PM, Michael Chen > wrote: > > --this is my first version for the purpose of storing sparse numerical > > matrix in sql > > --please let me know how to fix the bug at the end of the file, and how > to > > tune the performance > > --or any better reference, thanks! > > > > .explain-- return result in more readable > > format > > .echo on-- echo the sql stmnt > > > > --I plan to store my sparse matrix (3 x 4) in table like this: > > -- [ 1 2 0 0 ] > > -- [ 0 3 9 0 ] > > -- [ 0 1 4 0 ] > > -- > > -- is a three-by-four matrix with six nonzero elements, so > > -- > > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order > > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element > of > > row i in A > > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero > element > > A(i) > > -- > > -- Note: In this example, the row and line index begin by 1 and not 0. > > > > create table rowids( > > rows integer primary key -- there should be an easy way for a sequence > > 1..M? > > ); > > > > insert into rowids values (1); > > insert into rowids values (2); > > insert into rowids values (3); > > > > create table colids( > > cols integer primary key -- there should be an easy way for a sequence > > 1..N? > > ); > > > > insert into colids values (1); > > insert into colids values (2); > > insert into colids values (3); > > insert into colids values (4); > > > > > > create table matrix( > > rowid integer reference rowids, > > colid integer reference colids, > > value real non null > > ); > > > > insert into matrix values (1,1,1); > > insert into matrix values (1,2,2); > > insert into matrix values (2,2,3); > > insert into matrix values (2,3,9); > > insert into matrix values (3,2,1); > > insert into matrix values (3,3,4); > > insert into matrix values (2,4,0); --this entry is inserted on purpose > > > > > > select * from matrix; > > > > > > --A rowwise sparse matrix is then: > > > > create temp view rowwiseA as > > select value as A, colid as JA from matrix > > where value != 0 > > order by rowid, colid > > ; > > > > create temp view rowwiseB as > > select rowid, count(rowid) as ct > > from matrix > > where value != 0 > > group by rowid > > order by rowid > > ; > > > > create temp view rowwiseC as > > select a1.rowid, sum(a2.ct) +1 as JA > > from rowwiseB a1, rowwiseB a2 > > where a2.rowid < a1.rowid > > group by a1.rowid > > ; > > --this is not quite right yet, the first entry and last entry of JA > vector > > is not here. > > > > select * from rowwiseA; > > select * from rowwiseB; > > select * from rowwiseC; > > > > > > create temp view rowwiseB as > > select count(rowid) as ia from matrix > > where value != 0 > > group by rowid > > order by rowid > > ; > > > > > > > > --Best regards, > > --Michael Chen > > --Google Voice Phone.: 847-448-0647 > > ___ > > sqlite-users mailing list > > sqlite-users@sqlite.org > > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > > > > > -- > Puneet Kishor http://www.punkish.org > Carbon Model http://carbonmodel.org > Charter Member, Open Source Geospatial Foundation http://www.osgeo.org > Science Commons Fellow, http://sciencecommons.org/about/whoweare/kishor > Nelson Institute, UW-Madison http://www.nelson.wisc.edu > --- > Assertions are politics; backing up assertions with evidence is science > === > Sent from Madison, WI, United States > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- Best regards, Michael Chen Google Voice Phone.: 847-448-0647 ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] sparse matrix in scientific computing with sqlite
thanks Pavel ! On Fri, Oct 16, 2009 at 1:24 PM, Pavel Ivanov wrote: > > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element > of > > row i in A > > Why 4th element if A has only 3 rows? > > > create temp view rowwiseC as > > select a1.rowid, sum(a2.ct) +1 as JA > > from rowwiseB a1, rowwiseB a2 > > where a2.rowid < a1.rowid > > group by a1.rowid > > ; > > --this is not quite right yet, the first entry and last entry of JA > vector > > is not here. > > You want it like this: > > select a1.rowid, ifnull(sum(a2.ct), 0) + 1 as IA > from rowwiseB a1 left outer join rowwiseB a2 on a2.rowid < a1.rowid > group by a1.rowid; > > > Pavel > > On Fri, Oct 16, 2009 at 2:09 PM, Michael Chen > wrote: > > --this is my first version for the purpose of storing sparse numerical > > matrix in sql > > --please let me know how to fix the bug at the end of the file, and how > to > > tune the performance > > --or any better reference, thanks! > > > > .explain-- return result in more readable > > format > > .echo on-- echo the sql stmnt > > > > --I plan to store my sparse matrix (3 x 4) in table like this: > > -- [ 1 2 0 0 ] > > -- [ 0 3 9 0 ] > > -- [ 0 1 4 0 ] > > -- > > -- is a three-by-four matrix with six nonzero elements, so > > -- > > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order > > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element > of > > row i in A > > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero > element > > A(i) > > -- > > -- Note: In this example, the row and line index begin by 1 and not 0. > > > > create table rowids( > > rows integer primary key -- there should be an easy way for a sequence > > 1..M? > > ); > > > > insert into rowids values (1); > > insert into rowids values (2); > > insert into rowids values (3); > > > > create table colids( > > cols integer primary key -- there should be an easy way for a sequence > > 1..N? > > ); > > > > insert into colids values (1); > > insert into colids values (2); > > insert into colids values (3); > > insert into colids values (4); > > > > > > create table matrix( > > rowid integer reference rowids, > > colid integer reference colids, > > value real non null > > ); > > > > insert into matrix values (1,1,1); > > insert into matrix values (1,2,2); > > insert into matrix values (2,2,3); > > insert into matrix values (2,3,9); > > insert into matrix values (3,2,1); > > insert into matrix values (3,3,4); > > insert into matrix values (2,4,0); --this entry is inserted on purpose > > > > > > select * from matrix; > > > > > > --A rowwise sparse matrix is then: > > > > create temp view rowwiseA as > > select value as A, colid as JA from matrix > > where value != 0 > > order by rowid, colid > > ; > > > > create temp view rowwiseB as > > select rowid, count(rowid) as ct > > from matrix > > where value != 0 > > group by rowid > > order by rowid > > ; > > > > create temp view rowwiseC as > > select a1.rowid, sum(a2.ct) +1 as JA > > from rowwiseB a1, rowwiseB a2 > > where a2.rowid < a1.rowid > > group by a1.rowid > > ; > > --this is not quite right yet, the first entry and last entry of JA > vector > > is not here. > > > > select * from rowwiseA; > > select * from rowwiseB; > > select * from rowwiseC; > > > > > > create temp view rowwiseB as > > select count(rowid) as ia from matrix > > where value != 0 > > group by rowid > > order by rowid > > ; > > > > > > > > --Best regards, > > --Michael Chen > > --Google Voice Phone.: 847-448-0647 > > ___ > > sqlite-users mailing list > > sqlite-users@sqlite.org > > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- Best regards, Michael Chen Google Voice Phone.: 847-448-0647 ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] sparse matrix in scientific computing with sqlite
> -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element of > row i in A Why 4th element if A has only 3 rows? > create temp view rowwiseC as > select a1.rowid, sum(a2.ct) +1 as JA > from rowwiseB a1, rowwiseB a2 > where a2.rowid < a1.rowid > group by a1.rowid > ; > --this is not quite right yet, the first entry and last entry of JA vector > is not here. You want it like this: select a1.rowid, ifnull(sum(a2.ct), 0) + 1 as IA from rowwiseB a1 left outer join rowwiseB a2 on a2.rowid < a1.rowid group by a1.rowid; Pavel On Fri, Oct 16, 2009 at 2:09 PM, Michael Chen wrote: > --this is my first version for the purpose of storing sparse numerical > matrix in sql > --please let me know how to fix the bug at the end of the file, and how to > tune the performance > --or any better reference, thanks! > > .explain -- return result in more readable > format > .echo on -- echo the sql stmnt > > --I plan to store my sparse matrix (3 x 4) in table like this: > -- [ 1 2 0 0 ] > -- [ 0 3 9 0 ] > -- [ 0 1 4 0 ] > -- > -- is a three-by-four matrix with six nonzero elements, so > -- > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element of > row i in A > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero element > A(i) > -- > -- Note: In this example, the row and line index begin by 1 and not 0. > > create table rowids( > rows integer primary key -- there should be an easy way for a sequence > 1..M? > ); > > insert into rowids values (1); > insert into rowids values (2); > insert into rowids values (3); > > create table colids( > cols integer primary key -- there should be an easy way for a sequence > 1..N? > ); > > insert into colids values (1); > insert into colids values (2); > insert into colids values (3); > insert into colids values (4); > > > create table matrix( > rowid integer reference rowids, > colid integer reference colids, > value real non null > ); > > insert into matrix values (1,1,1); > insert into matrix values (1,2,2); > insert into matrix values (2,2,3); > insert into matrix values (2,3,9); > insert into matrix values (3,2,1); > insert into matrix values (3,3,4); > insert into matrix values (2,4,0); --this entry is inserted on purpose > > > select * from matrix; > > > --A rowwise sparse matrix is then: > > create temp view rowwiseA as > select value as A, colid as JA from matrix > where value != 0 > order by rowid, colid > ; > > create temp view rowwiseB as > select rowid, count(rowid) as ct > from matrix > where value != 0 > group by rowid > order by rowid > ; > > create temp view rowwiseC as > select a1.rowid, sum(a2.ct) +1 as JA > from rowwiseB a1, rowwiseB a2 > where a2.rowid < a1.rowid > group by a1.rowid > ; > --this is not quite right yet, the first entry and last entry of JA vector > is not here. > > select * from rowwiseA; > select * from rowwiseB; > select * from rowwiseC; > > > create temp view rowwiseB as > select count(rowid) as ia from matrix > where value != 0 > group by rowid > order by rowid > ; > > > > --Best regards, > --Michael Chen > --Google Voice Phone.: 847-448-0647 > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] sparse matrix in scientific computing with sqlite
This is not the answer you are looking for, and there are SQL geniuses on this list who will help you better, but really, is an rdbms really a good place to store a matrix the way you are trying to do? So convoluted. My approach, if I really was determined to store it in sqlite, would be to flatten the matrix in my code, and then stuff that into a table. Retrieve it and deserialize it as needed. For example, Perl's freeze, thaw are tailor made for this kind of stuff. On Fri, Oct 16, 2009 at 1:09 PM, Michael Chen wrote: > --this is my first version for the purpose of storing sparse numerical > matrix in sql > --please let me know how to fix the bug at the end of the file, and how to > tune the performance > --or any better reference, thanks! > > .explain -- return result in more readable > format > .echo on -- echo the sql stmnt > > --I plan to store my sparse matrix (3 x 4) in table like this: > -- [ 1 2 0 0 ] > -- [ 0 3 9 0 ] > -- [ 0 1 4 0 ] > -- > -- is a three-by-four matrix with six nonzero elements, so > -- > -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order > -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element of > row i in A > -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero element > A(i) > -- > -- Note: In this example, the row and line index begin by 1 and not 0. > > create table rowids( > rows integer primary key -- there should be an easy way for a sequence > 1..M? > ); > > insert into rowids values (1); > insert into rowids values (2); > insert into rowids values (3); > > create table colids( > cols integer primary key -- there should be an easy way for a sequence > 1..N? > ); > > insert into colids values (1); > insert into colids values (2); > insert into colids values (3); > insert into colids values (4); > > > create table matrix( > rowid integer reference rowids, > colid integer reference colids, > value real non null > ); > > insert into matrix values (1,1,1); > insert into matrix values (1,2,2); > insert into matrix values (2,2,3); > insert into matrix values (2,3,9); > insert into matrix values (3,2,1); > insert into matrix values (3,3,4); > insert into matrix values (2,4,0); --this entry is inserted on purpose > > > select * from matrix; > > > --A rowwise sparse matrix is then: > > create temp view rowwiseA as > select value as A, colid as JA from matrix > where value != 0 > order by rowid, colid > ; > > create temp view rowwiseB as > select rowid, count(rowid) as ct > from matrix > where value != 0 > group by rowid > order by rowid > ; > > create temp view rowwiseC as > select a1.rowid, sum(a2.ct) +1 as JA > from rowwiseB a1, rowwiseB a2 > where a2.rowid < a1.rowid > group by a1.rowid > ; > --this is not quite right yet, the first entry and last entry of JA vector > is not here. > > select * from rowwiseA; > select * from rowwiseB; > select * from rowwiseC; > > > create temp view rowwiseB as > select count(rowid) as ia from matrix > where value != 0 > group by rowid > order by rowid > ; > > > > --Best regards, > --Michael Chen > --Google Voice Phone.: 847-448-0647 > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- Puneet Kishor http://www.punkish.org Carbon Model http://carbonmodel.org Charter Member, Open Source Geospatial Foundation http://www.osgeo.org Science Commons Fellow, http://sciencecommons.org/about/whoweare/kishor Nelson Institute, UW-Madison http://www.nelson.wisc.edu --- Assertions are politics; backing up assertions with evidence is science === Sent from Madison, WI, United States ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] sparse matrix in scientific computing with sqlite
--this is my first version for the purpose of storing sparse numerical matrix in sql --please let me know how to fix the bug at the end of the file, and how to tune the performance --or any better reference, thanks! .explain-- return result in more readable format .echo on-- echo the sql stmnt --I plan to store my sparse matrix (3 x 4) in table like this: -- [ 1 2 0 0 ] -- [ 0 3 9 0 ] -- [ 0 1 4 0 ] -- -- is a three-by-four matrix with six nonzero elements, so -- -- A = [ 1 2 3 9 1 4 ] // List of non-zero matrix element in order -- IA = [ 1 3 5 7 ] // IA(i) = Index of the first nonzero element of row i in A -- JA = [ 1 2 2 3 2 3 ] // JA(i) = Column position of the non zero element A(i) -- -- Note: In this example, the row and line index begin by 1 and not 0. create table rowids( rows integer primary key -- there should be an easy way for a sequence 1..M? ); insert into rowids values (1); insert into rowids values (2); insert into rowids values (3); create table colids( cols integer primary key -- there should be an easy way for a sequence 1..N? ); insert into colids values (1); insert into colids values (2); insert into colids values (3); insert into colids values (4); create table matrix( rowid integer reference rowids, colid integer reference colids, value real non null ); insert into matrix values (1,1,1); insert into matrix values (1,2,2); insert into matrix values (2,2,3); insert into matrix values (2,3,9); insert into matrix values (3,2,1); insert into matrix values (3,3,4); insert into matrix values (2,4,0); --this entry is inserted on purpose select * from matrix; --A rowwise sparse matrix is then: create temp view rowwiseA as select value as A, colid as JA from matrix where value != 0 order by rowid, colid ; create temp view rowwiseB as select rowid, count(rowid) as ct from matrix where value != 0 group by rowid order by rowid ; create temp view rowwiseC as select a1.rowid, sum(a2.ct) +1 as JA from rowwiseB a1, rowwiseB a2 where a2.rowid < a1.rowid group by a1.rowid ; --this is not quite right yet, the first entry and last entry of JA vector is not here. select * from rowwiseA; select * from rowwiseB; select * from rowwiseC; create temp view rowwiseB as select count(rowid) as ia from matrix where value != 0 group by rowid order by rowid ; --Best regards, --Michael Chen --Google Voice Phone.: 847-448-0647 ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Sparse matrix
Hi All, Simon answered: Here's a less gruesome version - no cases. I've given no thought to performance comparisons. Thanks for the two great solutions you posted. Upon further investigation, those solutions assume that we want all like occurrences together, effectively sorting records in way that overrides the original view or table. The best solutions I've come up with so far require first enumerating the rows in the view (or table). In my separate email thread "Enumerating rows in a view", I mention two methods: 1. Deconstructing the "order by", replacing it with a series of inequality operators. Then counting how many other records are less than each current record. or: 2. Creating a temporary table, filling with the rows from the view, using the automatic rowid as the enumeration. So, for the example "Timetable" in this thread, where I said: and a view that sorts the data is: create view "Timetable Sorted" as select rowid, Day, Subject, Room, Teacher, Period from Timetable order by Day, Period ; enumerating the rows via each method would be: 1. Deconstructing order into inequalities: create view Enumerated as select count(*) as Sequence, * from Timetable as Current left join Timetable as Others where Current.Day > Others.Day or ( Current.Day = Others.Day and Current.Period >= Others.Period ) group by Current.Day, Current.Period ; or: 2. Creating a temporary table: create temporary table Enumerated1 as select * from "Timetable Sorted" ; create temporary view Enumerated as select rowid as Sequence, * from Enumerated1 ; Note, I've also used a temporary view just to provide a Sequence column containing the enumeration. This gives the same column name as method 1, so the actual Sparsing (below) can use the same syntax (ie Sequence instead of rowid). Each method gives the sorted view/table Enumerated as: SequenceDay Period Teacher RoomSubject -- -- -- -- -- -- 1 Monday 1 Ng A1 English 2 Monday 2 Peters A2 Maths 3 Monday 3 Peters A2 Computing 4 Monday 4 KentH1 Sport 5 Tuesday 1 Peters A2 Maths 6 Tuesday 2 Ng A1 History 7 Tuesday 3 Ng A1 English 8 Tuesday 4 Ng A1 History 9 Wednesday 1 Peters A2 Maths 10 Wednesday 2 KentH1 Sport 11 Wednesday 3 Who S2 Science 12 Wednesday 4 Smith S2 Science Now, on to replacing repeated values with null (ie showing a "sparse matrix") and counting the repetitions. Now that I have enumerated sorted rows, I can use the following method. I compare each Current value with the Previous value (ie the value that is enumerated as one less than the Current value). If it's the same as the previous, then it's a repetition which I replace with null. If it's different to the previous, then I show the value and the count of the same values from the current to the next change, or the bottom of the table. For the Day column, for example, I calculate the Day (Current.Day or null) and DayCount (count until the next change, or null) like this: select case when Previous.Day is null or Current.Day != Previous.Day then Current.Day else null end as Day, case when Previous.Day is null or Current.Day != Previous.Day then coalesce( ( select Sequence from Enumerated as Others where Current.Day != Others.Day and Others.Sequence >= Current.Sequence limit 1 ), Bottom ) - Current.Sequence else null end as DayCount from Enumerated as Current left join Enumerated as Previous on Current.Sequence - 1 = Previous.Sequence left join ( select max( Sequence ) + 1 as Bottom from Enumerated ) ; which gives the desired: Day DayCount -- -- Monday 4 . . . . . . Tuesday 4 . . . . . . Wednesday 4 . . . . . . (I've used . to show nulls) To build the complete matrix, ie for all columns, I duplicated the expressions above for Day and DayCount to make Room and RoomCount (replacing Day with Room), Subject and SubjectCount etc. The result looks like the desired: Day DC Room RC Subject SC Teacher TC Period -- --- --- -- --- -- --- -- Monday 4A11English 1Ng 11 . .A22Maths 1
Re: [sqlite] Sparse matrix
At 1:54 PM +1000 8/23/07, T&B wrote: Hi Darren, It seems to me that you have a flawed design. Displaying sparse like that should be a function of your application display code, not the database I had to chuckle that when I asked "How do I use this to do that", your solution was "you shouldn't have that and you should do it with something other than this" ;-) Not really helpful, but good for a chuckle. Fortunately Simon's replies helped me out. Hopefully my followup posting gives a better example. Tom, my answer was quite appropriate, considering your example, and I stand by it. It is very common that people asking for help are demonstrating that they are heading in a bad direction and want help in dealing with the result of that; I think it is more helpful to assist with the bigger picture than to necessarily support a bad direction. Or put another way, often when people want to solve problem A, then rather than asking for help in solving problem A, perhaps with some examples of what they tried, they assume that a certain way to go is best, and only ask for help in going that way, that is problem B. At 1:53 PM +1000 8/23/07, T&B wrote: But with counts of repetitions, like this: Day Room Subject TeacherPeriod MondayA1 1 English 1 Ng 1 1 A2 2 Maths 1 Peters 2 2 Computing 1 3 H1 1 Sport 1 Kent 1 4 Tuesday A2 1 Maths 1 Peters 1 1 A1 3 History 1 Ng 3 2 English 1 3 History 1 4 Wednesday A2 1 Maths 1 Peters 1 1 H1 1 Sport 1 Kent 1 2 S1 2 Science 2 Who1 3 Smith 1 4 The "1" counts could even appear as null/blank, that would be fine. Now your newer example does demonstrate a more reasonable problem to solve. By the looks of it you want to display results in a prettier or easier to read grid by having blanks rather than repeated field values; perhaps you are rendering an HTML table, and the numerical count you want is to provide a "rowspan" attribute value. If the DBMS can do this, then your HTML generator would be extremely simple. Or you aren't making HTML, but have similar issues. That said, if what you want is even possible with SQL, then it would probably be rather verbose SQL, involving multiple joins and group-bys and order-bys etc, and I suspect that your total code size would be smaller if you used appropriate logic in your application to blank the result fields rather than SQL. So I still recommend you do what you want in your presentation layer rather than in the data layer. -- Darren Duncan - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Sparse matrix
Hi Darren, It seems to me that you have a flawed design. Displaying sparse like that should be a function of your application display code, not the database I had to chuckle that when I asked "How do I use this to do that", your solution was "you shouldn't have that and you should do it with something other than this" ;-) Not really helpful, but good for a chuckle. Fortunately Simon's replies helped me out. Hopefully my followup posting gives a better example. Tom - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Sparse matrix
Hi Simon,
Here's a less gruesome version - no cases. I've given no thought to
performance comparisons.
Thanks for the two great solutions you posted. They certainly achieve
the desired result with the simplified sample I gave. However, in the
broader reality, it doesn't quite satisfy my situation since the
rowids aren't necessarily in the order that they appear in the final
view.
Here's a broader example.
Say I have a timetable like this:
rowid Day Period TeacherRoomSubject
1 Tuesday 1Peters A2 Maths
2 Monday2Peters A2 Maths
3 Monday1Ng A1 English
4 Monday3Peters A2 Computing
5 Tuesday 3Ng A1 English
6 Tuesday 2Ng A1 History
7 Wednesday 4Smith S2 Science
8 Wednesday 3Who S2 Science
9 Monday4KentH1 Sport
10 Wednesday 2KentH1 Sport
11 Tuesday 4Ng A1 History
12 Wednesday 1Peters A2 Maths
And I want to output something like this:
Day Room SubjectTeacherPeriod
MondayA1 EnglishNg 1
A2 Maths Peters 2
Computing 3
H1 Sport Kent 4
Tuesday A2 Maths Peters 1
A1 HistoryNg 2
English 3
History 4
Wednesday A2 Maths Peters 1
H1 Sport Kent 2
S1 ScienceWho3
Smith 4
But with counts of repetitions, like this:
Day Room Subject TeacherPeriod
MondayA1 1 English 1 Ng 1 1
A2 2 Maths 1 Peters 2 2
Computing 1 3
H1 1 Sport 1 Kent 1 4
Tuesday A2 1 Maths 1 Peters 1 1
A1 3 History 1 Ng 3 2
English 1 3
History 1 4
Wednesday A2 1 Maths 1 Peters 1 1
H1 1 Sport 1 Kent 1 2
S1 2 Science 2 Who1 3
Smith 1 4
The "1" counts could even appear as null/blank, that would be fine.
The SQL for my sample Timetable above is:
create table Timetable
(
Day text,
Period integer,
Teacher text,
Room text,
Subject text
)
;
insert into table values('Tuesday',1,'Peters','A2','Maths');
insert into table values('Monday',2,'Peters','A2','Maths');
insert into table values('Monday',1,'Ng','A1','English');
insert into table values('Monday',3,'Peters','A2','Computing');
insert into table values('Tuesday',3,'Ng','A1','English');
insert into table values('Tuesday',2,'Ng','A1','History');
insert into table values('Wednesday',4,'Smith','S2','Science');
insert into table values('Wednesday',3,'Who','S2','Science');
insert into table values('Monday',4,'Kent','H1','Sport');
insert into table values('Wednesday',2,'Kent','H1','Sport');
insert into table values('Tuesday',4,'Ng','A1','History');
insert into table values('Wednesday',1,'Peters','A2','Maths');
and a view that sorts the data is:
create view "Timetable Sorted"
as
select rowid, Day, Subject, Room, Teacher, Period
from Timetable
order by Day, Period
;
Thanks for any further insight you may have,
Tom
-
To unsubscribe, send email to [EMAIL PROTECTED]
-
Re: [sqlite] Sparse matrix
Hi Tom, Here's a less gruesome version - no cases. I've given no thought to performance comparisons. C:\Joinerysoft\JMS\dev\trunk> sqlite3 tst.db SQLite version 3.4.0 Enter ".help" for instructions sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'b' ); sqlite> insert into List values( 'b' ); sqlite> insert into List values( 'c' ); sqlite> insert into List values( 'c' ); sqlite> insert into List values( 'c' ); sqlite> select v.Code, v.count from sqlite> List as L sqlite> left join sqlite> (select (select L1.rowid from List as L1 where sqlite> L1.Code=L2.Code limit 1) as id, sqlite> Code, sqlite> count(Code) as count from List as L2 group by Code) as v sqlite> on L.rowid=v.id order by L.rowid; a|4 | | | b|2 | c|3 | sqlite> sqlite> Rgds, Simon On 22/08/07, T&B <[EMAIL PROTECTED]> wrote: > Hi all, > > OK, this one has me stumped. I've been staring at it too long. > > I have a table with a column like this: > > Code > a > a > a > a > b > b > c > c > c > > I want to output two columns, one showing the Code, another showing > the count of each code, but with a null wherever it was a repeat, > like this: > > Code Count > a 4 > . > . > . > b 2 > . > c 3 > . > . > > (Note I've used . to show a null) > > Any ideas? > > I can simply do this to show the count of each, but it doesn't show > the blank rows: > > select Code, count(*) as Count from List group by Code; > > Here's the test table: > > create table List( Code text ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'b' ); > insert into List values( 'b' ); > insert into List values( 'c' ); > insert into List values( 'c' ); > insert into List values( 'c' ); > > Thanks, > Tom > > > - > To unsubscribe, send email to [EMAIL PROTECTED] > - > > - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Sparse matrix
Hi Tom, Its a pretty gruesome bit of sql... C:\Joinerysoft\JMS\dev\trunk> sqlite3 tst.db SQLite version 3.4.0 Enter ".help" for instructions sqlite> create table List( Code text ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'a' ); sqlite> insert into List values( 'b' ); sqlite> insert into List values( 'b' ); sqlite> insert into List values( 'c' ); sqlite> insert into List values( 'c' ); sqlite> insert into List values( 'c' ); sqlite> sqlite> select ...>case rowid>(select rowid from List as L2 where L1.Code=L2.Code limit 1) ...>when 0 then L1.Code ...>else null end, ...>case rowid>(select rowid from List as L2 where L1.Code=L2.Code limit 1) ...>when 0 then ...> (select count(Code) from List as L2 where l1.Code=L2.Code) ...>else null end ...>from List as L1; a|4 | | | b|2 | c|3 | |sqlite> sqlite> Rgds, Simon On 22/08/07, T&B <[EMAIL PROTECTED]> wrote: > Hi all, > > OK, this one has me stumped. I've been staring at it too long. > > I have a table with a column like this: > > Code > a > a > a > a > b > b > c > c > c > > I want to output two columns, one showing the Code, another showing > the count of each code, but with a null wherever it was a repeat, > like this: > > Code Count > a 4 > . > . > . > b 2 > . > c 3 > . > . > > (Note I've used . to show a null) > > Any ideas? > > I can simply do this to show the count of each, but it doesn't show > the blank rows: > > select Code, count(*) as Count from List group by Code; > > Here's the test table: > > create table List( Code text ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'a' ); > insert into List values( 'b' ); > insert into List values( 'b' ); > insert into List values( 'c' ); > insert into List values( 'c' ); > insert into List values( 'c' ); > > Thanks, > Tom > > > - > To unsubscribe, send email to [EMAIL PROTECTED] > - > > - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Sparse matrix
It seems to me that you have a flawed design. You should just have a 2 column database to begin with, with a table like this: Code Count a 4 b 2 c 3 Rather than plain inserting or deleting rows, just sometimes insert or delete, you should instead increment or decrement counts, adding a row if its the first instance of the code, and removing the row if it would decrement to zero. Displaying sparse like that should be a function of your application display code, not the database, and it can easily do that using a simple for-loop or something for each fetched row, iterating on the count. -- Darren Duncan - To unsubscribe, send email to [EMAIL PROTECTED] -
[sqlite] Sparse matrix
Hi all, OK, this one has me stumped. I've been staring at it too long. I have a table with a column like this: Code a a a a b b c c c I want to output two columns, one showing the Code, another showing the count of each code, but with a null wherever it was a repeat, like this: Code Count a 4 . . . b 2 . c 3 . . (Note I've used . to show a null) Any ideas? I can simply do this to show the count of each, but it doesn't show the blank rows: select Code, count(*) as Count from List group by Code; Here's the test table: create table List( Code text ); insert into List values( 'a' ); insert into List values( 'a' ); insert into List values( 'a' ); insert into List values( 'a' ); insert into List values( 'b' ); insert into List values( 'b' ); insert into List values( 'c' ); insert into List values( 'c' ); insert into List values( 'c' ); Thanks, Tom - To unsubscribe, send email to [EMAIL PROTECTED] -
