From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 17858 invoked by alias); 19 Jan 2016 20:50:58 -0000 Mailing-List: contact gsl-discuss-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gsl-discuss-owner@sourceware.org Received: (qmail 17824 invoked by uid 89); 19 Jan 2016 20:50:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy=H*r:207.46.100, H*r:sk:mail-by, H*r:sk:na01-by, H*RU:sk:BN3PR03 X-HELO: na01-by2-obe.outbound.protection.outlook.com Received: from mail-by2on0148.outbound.protection.outlook.com (HELO na01-by2-obe.outbound.protection.outlook.com) (207.46.100.148) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA256 encrypted) ESMTPS; Tue, 19 Jan 2016 20:50:55 +0000 Authentication-Results: spf=none (sender IP is ) smtp.mailfrom=patrick.alken@colorado.edu; Received: from palken-co-ll.ngdc.noaa.gov (140.172.179.43) by BN3PR0301MB0900.namprd03.prod.outlook.com (10.160.156.142) with Microsoft SMTP Server (TLS) id 15.1.365.19; Tue, 19 Jan 2016 20:50:52 +0000 Subject: Re: Sparse matrix extension References: <569E6C33.1090505@colorado.edu> To: "gsl-discuss@sourceware.org" From: Patrick Alken Message-ID: <569EA1A9.2080101@colorado.edu> Date: Tue, 19 Jan 2016 20:50:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit X-ClientProxiedBy: DM2PR10CA0055.namprd10.prod.outlook.com (10.141.241.23) To BN3PR0301MB0900.namprd03.prod.outlook.com (25.160.156.142) X-MS-Office365-Filtering-Correlation-Id: 0d1c847e-495c-4362-6453-08d32112383d X-Microsoft-Exchange-Diagnostics: 1;BN3PR0301MB0900;2:dNPWDeuybaBgmdTBuKRi5KffE5q67crn7qhSRWj8C/8eHB1JZAIgM0m25PLL7Hh9bkPMeHgkP39yTo6C3BgAAs4LtSCFdiv+FERlWa/cqsJa1DnoQ/1rj1LD8csg465l+DJRElsWrUmqCFQHSsPo/jVP/yTRr3rhAruJFSQt+aVTMRiXI/uDbOzUFvz6QbnC;3:L2v6sIjZZZ6UP/q1YSBkyY2peG5/aQDv0fIXuYvVJ6WjsNO3hCetWtfPcLiYxKze+4uDw7ALXwJuqef479q3IwWXekzbP+j7FWyjFXMdNDtO4QG/T/FnBoLPwiopUIaK;25:gJBajENYYquZT6XyR5OZvGMot2D8ipoZRPAYSbLfYARpiqvZXuB0EGT/qOXj5j4OhDuheHUETV9iqNhAJDFOxefTgqYIaUXkWkr0nFyPW5af9F0ym+R6dZEeIVOU6AkC3llRB5UjFTveaWa0bvMNZGt2lfgdgcQhnKY70+Zi+8sT5sbGLcNGioRb27jVQYyqWRQBAcB3iyaz1Gu+ggLiVXId+Lj4X38CNkpqLaLQnukqCJPTL+jGOf+d97ikUNM/;4:JqG3B7FGzHjNoXuz8GTMAKqR+S4d0hM4CtTsndJ0XbqXgfHuuOgfCcivAWABNQJ2cffhi2vCvXBrKMcwO6OOdek/8Y4W7hOWmg6rbzVygiGsI2l9MH5F8BwbG5XWChA+fBVcqElUCDUq8riU8preyZDQkkkRg/KzRhu9KN3xoy9kiQo3eRD8wAAA71LqRSucJhOfDzLxH6HGelmgxiRxenB+5dCHsjhx51Mwlc8aKkV+fylHxppZK5jimbYyK/SkDkfha6kAUkYM/19+6dcjaPThBnJD/1eaIle8QUlNTqYPFNSFsqNekE47et392X3MCKKJRs1kC4++AXwmAC4OYKbPxvWqcoKI/7lO5u0m4PTGL05NSdn0QTijmHOe5yzY X-Exchange-Antispam-Report-Test: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN3PR0301MB0900;UriScan:; X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(520078)(8121501046)(5005006)(3002001)(10201501046);SRVR:BN3PR0301MB0900;BCL:0;PCL:0;RULEID:;SRVR:BN3PR0301MB0900; X-Forefront-PRVS: 0826B2F01B X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(6009001)(43784003)(52024003)(76104003)(479174004)(51914003)(377454003)(24454002)(485384002)(199003)(189002)(6116002)(66066001)(83506001)(23676002)(50466002)(65816999)(65806001)(15975445007)(105586002)(64126003)(65956001)(87976001)(54356999)(75432002)(93886004)(76176999)(89122001)(59896002)(47776003)(88552002)(19580395003)(19580405001)(80316001)(101416001)(42186005)(50986999)(106356001)(2351001)(36756003)(4001350100001)(87266999)(92566002)(586003)(110136002)(33656002)(1096002)(2501003)(40100003)(2906002)(107886002)(3846002)(90282001)(97736004)(5001960100002)(450100001)(5004730100002)(81156007)(122386002)(5008740100001)(230700001)(189998001)(2950100001)(77096005);DIR:OUT;SFP:1102;SCL:1;SRVR:BN3PR0301MB0900;H:palken-co-ll.ngdc.noaa.gov;FPR:;SPF:None;PTR:InfoNoRecords;A:1;MX:1;LANG:en; Received-SPF: None (protection.outlook.com: colorado.edu does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCTjNQUjAzMDFNQjA5MDA7MjM6cmRYQmFmVXFOY2hPamg5RGxyeGZRNUJR?= =?utf-8?B?dFhkOUpoTHVPKzhiYTk0T21iaW94cStBalNPTTFXaTdYaEtJb2RQbnVpcnJv?= =?utf-8?B?YUgxS3hlS3JEbFFST1prSDRMbGJCenZPRi9vRXlxc3ZHVzlKdDBxSVFXbDZa?= =?utf-8?B?KzFycGlMYnVITWk5dWcyYmYxd2doN3NzTHJheS9XeEQ2cy8yRzUxMVpIcGp6?= =?utf-8?B?VnRFRnB5Q3hyRmdpamc3cWVOVHlYeVB1ZmlUREQrcW1KVzBCOWZOMnR2czlY?= =?utf-8?B?MzFJQXJlM0lJRGpRSGUrZzZsWkIvMWtBNi9ZeGlOaXhtaUY4Wm5wNkVKU1N2?= =?utf-8?B?bUJuQ2hBdXlYK3I2em5jb2ZnSmE4VkJ6cmFoN2pSRnV3UDBBV1BLYlZJUHhQ?= =?utf-8?B?THVVRGFmdE9KV0U5SXlSb2N5RndTK05KdzNtUVdQV0drbTBRUlZQZUN2Zkp5?= =?utf-8?B?RkJseXMyWVRZcUVMbDNYQVEvVmthWm40MmNOOXNrVjdJSkVDa2tncjVzZ1FU?= =?utf-8?B?QWVWMkovSG9WakhFYlRML0k0QUJlNFZWcTVIcXhPejB1UjhxelU2Z2NvcTZW?= =?utf-8?B?UVJyQXJOeTVEQlpsdGdhdlZ1WDNYa0FaSERCbTY1cTV4bWhpaGZEK2VBZ0ZF?= =?utf-8?B?d0xhbmZGaG9zSVBqM2o2U3B4NXpES28rQ1RPcS9QL1BLeWRTcDA2ZllNaDM2?= =?utf-8?B?Nlp3Y3NPYnl2cVR6Qmt3cXg3eHdGdG9QaHlXemE0UTBtY1NiT1FwTW9iSDIz?= =?utf-8?B?MUozaUNuWEI4WE01NXNZS3NYMzB3eTBIdExiQVROZzZQekNYQ3VjRE00TG1Y?= =?utf-8?B?MVBTRVZQYmd1SVVLak4zYUlySWtUbzIwODVpQmZpYkFwNmlMU3hRNnZuMUxC?= =?utf-8?B?SGUrMXlEbjMzU0lZN25icXlMMS9DYU1qdStvK1Zhc1YvZWxTa0EyTkpBQ1Jp?= =?utf-8?B?aVpxOURzM2pEdDdNZ1Z3cDdwTzJSY29MZ0dyZkFXVzEzRmIzV2d4cVFYK0xC?= =?utf-8?B?WDA4YkxaRk42d0FvTjFZUlh1cG9nVDY5VXFEdXlPbnNseGlxaVdtcDVQcW5i?= =?utf-8?B?ajhvQnJ6R01rUStnMFB1Y3pJUkUwQnllV2FrUlNoTURFejNtRjkyOWhVRkdZ?= =?utf-8?B?ZXNoS0tXWXFkTUdaYXZkZTRqRE1sNk1HdkFCdytad2lYekR3YlNpa0EzekIv?= =?utf-8?B?NE9raEpoTVlRMWdUa2UyT3ROSzlHQ0F0NmJqeTZhOVJvMklnVGYvM3Bielg1?= =?utf-8?B?YTRpUERwR1JGNEtuVnh2T1M0RDQ5NmF3VmRTQUFLSmowbllSdHZkb05sNnBW?= =?utf-8?B?MzErbWdqdUtuVHg4cjI4TnJRc1VrOXBwbW1EQzJmN0dhcmh0T2dYbGE2YUhu?= =?utf-8?B?NDZ2dmVIZWFnUWdiNXAxK2wyQ2VXSGpRRVJoYkNMOGhzV2h0SWp3SEhYMXR4?= =?utf-8?B?MXp3SXhIOTNSNWNUbms0VUtXQU1QNkVPT3lwMktCUFowdmlEVXl2ZkxYYkpO?= =?utf-8?B?dStEakp6TWszVVQzbHdxVnE3TFBUeGVMcEJtcW5idnFBNWcyQzNHc2dwVWlw?= =?utf-8?B?YlU4bURhQ0I4NUdGVVk3WHRLZ0N1blUyWm1RNTZkNXd6OTNjMWJRUE9yT1B1?= =?utf-8?B?QmhnVisxaCtheFZRdzhsa0s5a1RIWmJvaGNza2dhQWdGTmJIZ1N4eEJkRzhB?= =?utf-8?B?aTU0bDI2bEM4M0lTNDhOSmU1bTBVU2FzYTdESzMxU0FLaHJhakhtUjJ6c0E2?= =?utf-8?B?RC91cFpRcTVhY1JHalA2YnlvdGxVWkF0a2RUb3VwNDBRMG96U1dWblVHSGZy?= =?utf-8?B?QXFIUThvZU5NRklwQnR3OTZJUlg5am9mdWJmNjFpTFJkWC9UU1ZaV1FhZEJj?= =?utf-8?B?bFJkNnF6YVg3MjFMZm9iaThmZ2hUMlg5U2p4bVFZM1E5cEJCdlRxdFc4TWR3?= =?utf-8?B?Y0hWcTU5V1VOd2hsbEtMa3VyR3p6R2FxNTVhWFNsQ3ZZeTNYeUhtYWR4RE1Z?= =?utf-8?B?dU9QVjFGZGJobTdZMXgyUEs0NGd0dHpDemMxTTJZbklSTDh2VjFBN21HTzhm?= =?utf-8?B?Mk03bG1rSWkvWUNicVJQWVEzbjNqbEFQN2sxNmlJcHZEYjg1SlZ3YSs0Sjhw?= =?utf-8?Q?ip/iqqtPSNB10TShuKINcx4vfL9LAziJnTRYffaCf9DiFw?= X-Microsoft-Exchange-Diagnostics: 1;BN3PR0301MB0900;5:53Y5qglrA+8rqvcFyMs/IObry9qfFc41XXfvq5tEeOlVBmFBtwUna9YFb9ID/qtlnf8KESo2Nm3t1KEOosWXfmEo5uWdwSlynxbFVazgppsD+jlQKrcKVdxYP/AU+EvJZcpCGWKjnN+li+agmXxImQ==;24:uB512qLsFmsfXu3j4y25WXInfNDCRMbvF+v9kufTJthKavS01Wk2VYXyejZ2x3owx9S3BIF2N74J68ARCds4AGEWtZtg+/Chh/5ePCCnmQU= SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: colorado.edu X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Jan 2016 20:50:52.4484 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN3PR0301MB0900 X-SW-Source: 2016-q1/txt/msg00003.txt.bz2 On 01/19/2016 12:55 PM, Alexis Tantet wrote: > Hi Patrick, > > Thanks for the quick reply! I wanted to be sure that this contribution > is useful before to spend time on the merging with the latest version. > I will create the gsl.git repository and work on it during the week. > > I had already had a look at the documentation but did not know about > the iterative solvers (a link between each modules would be useful). > My contribution indeed fits in the sparse matrix module + the update > of the dgemm and dgemv functions to support CRS (an update may also be > needed for the solvers). The solvers only call dgemv (as far as I remember) so they shouldn't need an update once dgemv is updated. > > I have also developed a simple C++ object allowing to use gsl_spmatrix > as a user-defined matrix in ARPACK++ (a maintained fork of ARPACK++ > can be found at https://github.com/m-reuter/arpackpp), allowing to > avoid having to use other libraries such as superLU. It could be > useful to others, maybe as an extension. Now that I think about it, > the iterative solvers could also be used to support the shift and > invert modes (see ARPACK++ documentation). What do you think (I could > work on it)? I've never used ARPACK, but if you want to make an extension to interface GSL/ARPACK its fine with me - such an extension would never be added to the main GSL code since GSL tries to be as standalone as possible. > > If you have major comments, the sooner the better, so that I can work > on them while merging. > > Thank you for your interest, > Alexis > > On Tue, Jan 19, 2016 at 6:02 PM, Patrick Alken wrote: >> Hi Alexis, >> >> This looks like very good work! Adding compressed row storage has been on >> my todo list for a while. The 'gslsp' extension is unfortunately very out of >> date, and the current git contains newer code (including a GMRES iterative >> linear solver). I removed the gslsp extension from the web page a while back >> to reflect this. You can browse the latest manual to see the current sparse >> matrix capabilities (http://www.gnu.org/software/gsl/manual/gsl-ref.pdf) - >> there are 3 chapters: sparse matrices, sparse blas and sparse linear algebra >> - it looks like your contributions will fit into the sparse matrices >> chapter. >> >> Would you be able to verify that your changes are compatible with the >> current gsl.git repository? This will make it much easier for me to merge >> everything into the git when ready. It would be best if you made a new >> branch of gsl.git, and add your changes so I can then pull them from github >> or somewhere. I will try to find some time in the next few days to look over >> your code. >> >> Thanks again, >> Patrick >> >> >> On 01/19/2016 09:43 AM, Alexis Tantet wrote: >>> Dear GSLers, >>> >>> As a scientist rather than a developer, I have developed an extension >>> of the sparse matrix module (CRS, I/O, manipulation, see below), which >>> I have tested. These modifications conserve the structure of the >>> original module and be useful for a large number of sparse matrices >>> users. >>> >>> I'm not familiar with the contributing process here. My repository can >>> be found there: >>> https://github.com/atantet/gslsp >>> Unfortunately, I did not know of the gsl.git repository and I forked it >>> froml: >>> https://github.com/drjerry/gslsp , >>> which seems to be a bit older than gsl.git. >>> >>> How can I push/merge to gsl.git ? Should it be as an update or another >>> extension? Is it necessary to adapt to the newest version of the code >>> ? >>> >>> Best regards, >>> Alexis Tantet >>> >>> CHANGES.md: >>> >>> Extension of the sparse matrix module of GSL >>> >>> =================================== >>> >>> Introduction >>> ------------ >>> >>> Usages of sparse matrices are numerous in scientific computing. >>> When numerical linear algebra problems become large, sparse >>> matrices become necessary to avoid memory overload and unnecessary >>> computations, at the cost of element access and matrix construction. >>> As a result, most large scale linear solvers or eigen solvers perform >>> on sparse matrices. >>> >>> Fortunately, a very useful sparse matrix module has recently been >>> introduced to GSL. >>> However, important features are still lacking, such has >>> Compressed Row Storage (CRS) matrices, input/output functions and >>> other matrix properties and manipulation functions. >>> This new version attempts to address this, conserving the original >>> structure of the module and conventions. >>> >>> Major changes >>> ------------- >>> >>> * Add CRS format and update functions manipulating compressed matrices : >>> - additional flag GSL_SPMATRIX_CRS and macro GSLSP_ISMATRIX ( >>> gsl_spmatrix.h ) >>> - additional members innerSize and outerSize used to iterate >>> matrix elements ( gsl_spmatrix.h ) >>> - rename some variables for coherence ( gsl_spmatrix.h , *.c ) >>> - update all functions on compressed matrices ( *.c ) >>> * Allow to sum duplicate elements when compressing ( spcompress.c ) : >>> - modify gsl_spmatrix_compress >>> - add gsl_spmatrix_sum_duplicate >>> * CCS <-> CRS and fast transpose inplace in spswap.c : >>> - add gsl_spmatrix_switch_major >>> - add gsl_spmatrix_transpose >>> * Add printing and scanning functions in spio.c : >>> - add gsl_spmatrix_fprintf >>> - add gsl_spmatrix_fscanf >>> * Add manipulation functions in spmanip.c (particularly useful for >>> Markov chain transition matrices) : >>> - add gsl_spmatrix_get_rowsum : get vector of sum over row elements >>> - add gsl_spmatrix_get_colsum : get vector of sum over column >>> elements >>> - add gsl_spmatrix_div_rows : divide all elements of each row >>> by a vector element >>> - add gsl_spmatrix_div_cols : divide all elements of each >>> column by a vector element >>> * Add test functions in atprop.c : >>> - add gsl_spmatrix_gt_elements : greater than test for each matrix >>> element >>> - add gsl_spmatrix_ge_elements : greater or equal than test for >>> each matrix element >>> - add gsl_spmatrix_lt_elements : lower than test for each matrix >>> element >>> - add gsl_spmatrix_le_elements : lower or equal than test for >>> each matrix element >>> - add gsl_spmatrix_any : test if any non-zero element in >>> matrix >>> >>> Other minor changes have been made, such as error tests. >>> test.c has also been updated to test new features. >> > >