From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 55563 invoked by alias); 14 Feb 2016 18:11:00 -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 55549 invoked by uid 89); 14 Feb 2016 18:10:59 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy=market X-HELO: na01-by2-obe.outbound.protection.outlook.com Received: from mail-by2on0119.outbound.protection.outlook.com (HELO na01-by2-obe.outbound.protection.outlook.com) (207.46.100.119) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA256 encrypted) ESMTPS; Sun, 14 Feb 2016 18:10:56 +0000 Authentication-Results: sourceware.org; dkim=none (message not signed) header.d=none;sourceware.org; dmarc=none action=none header.from=colorado.edu; Received: from [192.168.0.75] (75.166.52.243) by BY1PR0301MB0902.namprd03.prod.outlook.com (10.160.195.141) with Microsoft SMTP Server (TLS) id 15.1.403.16; Sun, 14 Feb 2016 18:10:52 +0000 Subject: Re: Sparse matrix extension To: Alexis Tantet References: <569E6C33.1090505@colorado.edu> <569EA1A9.2080101@colorado.edu> <56B689B1.5090005@colorado.edu> <56B77E13.1000306@colorado.edu> <56B7A59D.5040707@colorado.edu> <56B7B85C.10508@colorado.edu> <56BB5D84.20804@colorado.edu> <56BF86FC.8010509@colorado.edu> CC: "gsl-discuss@sourceware.org" From: Patrick Alken Message-ID: <56C0C326.8090701@colorado.edu> Date: Sun, 14 Feb 2016 18:11:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-ClientProxiedBy: BLUPR14CA0065.namprd14.prod.outlook.com (25.163.209.161) To BY1PR0301MB0902.namprd03.prod.outlook.com (25.160.195.141) X-MS-Office365-Filtering-Correlation-Id: 8d7b6584-02f6-4549-9339-08d3356a2d82 X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0902;2:zjjcoMmdpIhZDkdKVAiJVCC8I5g1BItyaiozZZbmoc/62Y7mrJ63CYdLxQDggvXfRDcnZem3Nsr8XBmpiKIRY0P9ka6Xf52R9gsIV/agjtzGM6vyfxTc2GRvzo8Y1mPydxodrL9jsjpN56IMcBBqyiYitE495ViGPOpYb5QBnafvfKhUmcq+c+heAh8JbRDx;3:YUgrg8hhdD8SD95t81KdnFxbElvuWFrN9YXqRAgJ3NzDLiDgS0Hnkmr+fREB5SwbFA4FB/iCVSuieWwRV4ryJjmvYnwTfClBo8uC1p3Ms/SIbX37mmoA/5NBGWFZaLJ5;25:kYY8B8DusCOu7o8sH5ma2j6IMr3llViaRRv/2uE1Q05fZdzkMK1mH9IyaXlLm2Y96Lg9G12P+uj8QcBpxVezWHsMkhV9Sqd2GO7Dnj1UFW2SYDvNzpn9RJyGYLFMF3Jk475NXyBum7bIutmrNo2AUbFobsb5OW3cR/zdSv3JjS1bmn9gt/TvnQK6WXWC5F8y/IT1EecrPz1gvlc+zJ68t1A0iNO5cvmUaiNxMTMtIAQ0fbFexfUXg7cTF2JYBtu4GmzJIuYGxzJ5FaXZgwyqHs9zDBzzBtxf0a0AgmpNlAyHB8h+XeWOpNuyW1g1Yg61 X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BY1PR0301MB0902; X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:(65766998875637); X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001);SRVR:BY1PR0301MB0902;BCL:0;PCL:0;RULEID:;SRVR:BY1PR0301MB0902; X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0902;4:728XFIJTj6pZm+xII7Ud4Yb0xw6t8FXI7pt/b5cfgA8YqTD7g+hVSDFZtSQbdlfEmcAd20hwKTCtZa77r60PYr+0hIth4J+8vVIkshyTp8mMb+ROu4N1FwsbrNXx9Aadu2FzMvKzXdSbxMwzTVljGsJKqwOQM5RZZnOQd05kOL36QO8BmVphQURRMRHxFvGZZrtB636ynfI018exECAs3BG8AHVAolCJE8yflMXpFgrOcI/vbmivnAN0nQuepCtok9xY7F/aJu/Cd3mX4c2qika3O3p+qbPWlPz9BTgf0hRTiVvus5MoyX/OG5kDNoik/NtYyypi4dFCe3xf9fob46CCO6VdFHv0x/LFCMhruqHtdMeoiJT2qJZI2nqRM73LkqQL1VbLblgIXJ9i8e5n3nw0EFezAa9vHyz4r1x67OM= X-Forefront-PRVS: 0852EB6797 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(4630300001)(6049001)(6009001)(479174004)(51914003)(377454003)(24454002)(33656002)(90282001)(59896002)(117156001)(586003)(6116002)(3846002)(122386002)(40100003)(1096002)(36756003)(80316001)(5008740100001)(230700001)(5004730100002)(50466002)(93886004)(19580395003)(19580405001)(42186005)(89122001)(66066001)(54356999)(50986999)(76176999)(110136002)(92566002)(83506001)(65816999)(87976001)(75432002)(47776003)(2950100001)(2906002)(4326007)(4001350100001)(5001960100002)(15975445007)(77096005)(88552002)(64126003)(189998001)(3480700003)(23676002);DIR:OUT;SFP:1102;SCL:1;SRVR:BY1PR0301MB0902;H:[192.168.0.75];FPR:;SPF:None;MLV:sfv;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCWTFQUjAzMDFNQjA5MDI7MjM6bDUzaW84eDJOWXM3TmdSOHMrb1hRb2dy?= =?utf-8?B?WUZHd0dtUmFwcjF2MWhIcWRLL2NmWWdRYTdnWlV4OThESDZ5emRRWG83ZEdX?= =?utf-8?B?cU9XZ1dQY2luSWNrSjBnTDZJcWJseTF3ckdERnRsZmhneFkyU05CeDg4Q0Zl?= =?utf-8?B?VTFIaW1VYTZQdTRhZWpQa1FKSmd4VmE1Y0JSdnJHalp2Qk9qdTBoam9YeEEw?= =?utf-8?B?RGkvb1JUVU5qaU5jaGhDNk9PN1IraVV3WEhYQWdPZWhHZ0xMaUU2KzJrblJG?= =?utf-8?B?VURadWJQZjM1OUxLY0szQlVUNTFJVGN4WVFITHJCV0prVTR4OEtnTDdyUEZP?= =?utf-8?B?eFBWMGZXZHJKOWxVMG5MQm5iN1NINVl4WVhmOVpKeE1PV3FWSldoN2tGeVcr?= =?utf-8?B?alZ1bUF5TzE3ekVFNVdaVVlMemtGVzJncDQ5RmE5V2V2aFI3bFFES1grc0ZF?= =?utf-8?B?djRYQmhnc3BtYlZKR01UUmc5N3dDNHptSDFOdVdBWlRHWSt6ZERTSEpraXFP?= =?utf-8?B?S2FaeExRVTY4N1NMNCtsWWp4dTlXcW16TDFTL3dpaXhyeU11bWlCcVRpaFNO?= =?utf-8?B?MG9LNHI3VXRZRlZ3ZzEzcm13cVVjV2lJajhKZDdwV3pyK2NhekU4anNtT3RW?= =?utf-8?B?Ni9VSkp0cTAvVzNVQmd5SmtNK1AvUmtlZUNaVVJTc2ZrMEFSbmdIbFFTNlI4?= =?utf-8?B?b2J0Y1VIRHYyd1Bxd2pFTWI3QlJCY09PbTB2VTE1S1l2QVVtMDZhbk9NSktN?= =?utf-8?B?cDUwaXl2dUhOY21FYVcwZnRHbDBHMTJJaUd0bjhNck5WRnJzUFYybWhGM295?= =?utf-8?B?SmtVaGNYUDI3Z2JxTTZHcExuSjI0M1c5R3ZRdy9IYkxjQmRmVmRtaFdtejhi?= =?utf-8?B?aXJzVTE3ZVdQbWhTTjdBWUIrSmtmQXB3dHB1N0tnNFBScFJZT0orTlAxNS9K?= =?utf-8?B?YlY1NGFHZ1NJTk9JSXVXUDZlSWRTbTZFeS9KQUFuOWdKUG5Wd1pUWjBXRkpz?= =?utf-8?B?ZWlUdEFNVkgzWmRJSkxWN0U5cm10b0E1bU1pOXNVWllybXE2TXhXNXRuZjRZ?= =?utf-8?B?NjU3VWZ2WjROSDRDMkxTblJTaWNkNE1EYnZFWjNoS1VHMjVURVJqdloyN1pC?= =?utf-8?B?YVhDckpNMEQ5MDU1anRITy9FRWtMN1VsM3AzK055VXIwalBrRXZsR1Bhc0c5?= =?utf-8?B?ZnZQNXdtVjU2VEczNUNBN0NEVzVJSko2TXNTQm83YkxqbXBORkYrbm5YWmlq?= =?utf-8?B?YTdqL2tRa3EzL29nd0RWU0pQOHJuRE5yWlA3Z3cwbmhIWkQ3aHFPTkN0WVJa?= =?utf-8?B?Yjg5cE5leHk4K3hPWVJZWE00Ty9DRkh6TmJEaFNxQ0ZBMTJ2MmhyQWJqaUdl?= =?utf-8?B?aXJBK2VjdkVGZlZ0bEgwNlJCVFBuZnZrRlJKWnBvMHZMSUNDUnRsb3RyeTRQ?= =?utf-8?B?ekI5dENlWWVYbzF2eDZrd3dwSFRCellsVExBanowTTlSUmtMK0xsMXhFRUZD?= =?utf-8?B?OHlxb3hDNm5ocURiaGJHTkJpSG1zN25CQmFmZ1M5NTR4ekNidEhPWmNOSTV5?= =?utf-8?B?amJZdS83TFZGTEt5aXEybkR5NmREdUp5cVMydzNJZWhmL2dMTUpxZVBGNGVY?= =?utf-8?B?VGgzWkV5eXM3alV3bStMbGJKTzRsWE5Hbm9ISXBkUHhYc0R2QmVONnNDZlFi?= =?utf-8?B?dlRKdldERU9GK2JpbHZPTWNVUk9MNFdzb243WHBwbkRoT01Rc1JXVlFoY0cw?= =?utf-8?Q?onhg9HP5VUpqY2frrDIEl54eJ3M+b8jb4VkAroc=3D?= X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0902;5:cighvqfxknwx4bQCElKRvhTNsmKAlHL8P0TxNXBWTWVCHVzwmqPRETnW9TooaZCkod6MXk8KtW7R8R2Vlpt5iLJQ912CGdWrYK+xmg1PDUohGVMIb13+3bLwJLvnkitrTYOd5gPLA4HwMxbbD8JmvQ==;24:UDO6ihmE2Hy76blRA//sLAX7uxKYB/Q4GFu2aRiSDtT7cf7q9X+kUW2/uEP9lOZGQVbnrM0eO7+0k8tEjuEDUg7q1EskkENDGKijA9D9Iew= SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: colorado.edu X-MS-Exchange-CrossTenant-OriginalArrivalTime: 14 Feb 2016 18:10:52.9459 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY1PR0301MB0902 X-SW-Source: 2016-q1/txt/msg00019.txt.bz2 Ok fixed On 02/14/2016 04:06 AM, Alexis Tantet wrote: > Great! > > I've just figured that the printf/scanf need a modification. I had the > indices starting from 0 as in C, while the MatrixMarket standard > starts from 1. It is just a matter of adding one to the indices in > printf and removing one for scanf. Could you take care of it? > > On Sat, Feb 13, 2016 at 8:41 PM, Patrick Alken wrote: >> Ok I've added the MatrixMarket stuff to fprintf/fscanf. I also merged >> all the new sparse matrix stuff into the master branch on git. >> >> I've added almost your whole patch, except for all the stuff in >> spmanip.c and also the gt_elements() routines in spprop.c. I'm not sure >> these routines belong in a general purpose matrix library....although I >> can possibly see a need for the row/col multiplication stuff, since we >> can't easily make vector views of rows/columns of sparse matrices.. >> >> I'll need to think some more about this. >> >> Also I haven't yet modified dgemm, because I'm hesitant to use the >> dynamic allocation method in your patch. Also I found a sparse blas >> document on netlib which tries to outline a standard and I realize our >> sparse blas routines don't adhere to this standard...so I may try to >> redesign everything to follow that document. >> >> Anyway thanks a lot for all your work on this. >> >> Patrick >> >> On 02/12/2016 03:42 AM, Alexis Tantet wrote: >>> I corrected _fscanf. There was an error when reading the comment header. >>> >>> On Wed, Feb 10, 2016 at 4:55 PM, Patrick Alken wrote: >>>> I'm in favor of simplicity and easy-parsing, so matrix market sounds good to >>>> me. I'll take a look at your latest code in the next few days. >>>> >>>> Patrick >>>> >>>> >>>> On 02/10/2016 06:16 AM, Alexis Tantet wrote: >>>>> Hi Patrick, >>>>> >>>>> Regarding the file format for sparse matrices, the one I have coded >>>>> actually happen to be the coordinate format implemented by Matrix >>>>> Market (the platform to share test data such as sparse matrices), with >>>>> the addition of a matrix type header: >>>>> http://math.nist.gov/MatrixMarket/formats.html >>>>> >>>>> It is also written that "Harwell-Boeing" is the most commonly used >>>>> sparse matrix format, but that: >>>>> "Unfortunately the HB specification is somewhat complex difficult to >>>>> parse from languages other than Fortran, biased in favor of compressed >>>>> column representation and not easily extensible. Some of these factors >>>>> may have impeded the more widespread use of the HB format" >>>>> >>>>> It seems to me that complying to the Matrix Market coordinate format >>>>> would be the right choice, in terms of ease of implementation, >>>>> compliance to other packages and user-friendliness. I could update the >>>>> print/scan functions accordingly (mostly handling the header). What do >>>>> you think? >>>>> >>>>> Best, >>>>> Alexis >>>>> >>>>> >>>>> >>>>> >>>>> On Mon, Feb 8, 2016 at 1:59 AM, Alexis Tantet >>>>> wrote: >>>>>> Ok, my mistake, now I see where I got confused. >>>>>> I had in mind to add all the elements first to the triplets and only >>>>>> while converting to compressed sum up the duplicates. >>>>>> While, indeed, if there's a way you can sum up the duplicates directly >>>>>> while adding them to the triplet matrix (thanks to _ptr), this is more >>>>>> handy and efficient. >>>>>> >>>>>> Thanks for the clarification, >>>>>> Alexis >>>>>> >>>>>> On Sun, Feb 7, 2016 at 10:34 PM, Patrick Alken >>>>>> wrote: >>>>>>> By design, gsl_spmatrix_set won't allow you to do this. >>>>>>> >>>>>>> If you add element (i, j, x) and then later to try add element (i, j, >>>>>>> y), gsl_spmatrix_set will detect that there exists an element in the (i, >>>>>>> j) spot and it will simply change x to y - the value of x will be >>>>>>> overwritten by y. This is the same behavior as gsl_matrix_set. >>>>>>> >>>>>>> So no duplicates are allowed by design. If you have such an application >>>>>>> where you want to keep track of duplicates, you could do the following: >>>>>>> >>>>>>> double *ptr = gsl_spmatrix_ptr(m, i, j); >>>>>>> if (ptr) >>>>>>> *ptr += x; /* sum duplicate values */ >>>>>>> else >>>>>>> gsl_spmatrix_set(m, i, j, x); /* initalize to x */ >>>>>>> >>>>>>> On 02/07/2016 01:31 PM, Alexis Tantet wrote: >>>>>>>> I'm not sure I got your last point. I have the following situation in >>>>>>>> mind: >>>>>>>> >>>>>>>> Start to construct a transition matrix in triplet format, adding one >>>>>>>> element after another. >>>>>>>> In this particular example, each element is one count of a transition >>>>>>>> from (state, box, etc.) i to j, >>>>>>>> so I add elements (i, j, 1) to the triplet object, with possibly >>>>>>>> duplicates. >>>>>>>> What happen to these duplicates in the binary tree? >>>>>>>> >>>>>>>> Eventually, when I compress to CRS or CCS, I would like the duplicates >>>>>>>> to be summed up, so that element (i, j) counts transitions from i to j >>>>>>>> (and no duplicates exist after compression). >>>>>>>> >>>>>>>> Is this more clear? >>>>>>>> >>>>>>>> On Sun, Feb 7, 2016 at 9:14 PM, Patrick Alken >>>>>>>> wrote: >>>>>>>>> Hi Alexis, >>>>>>>>> >>>>>>>>>>> I'm not sure what you mean. I've added a new function >>>>>>>>>>> gsl_spmatrix_ptr >>>>>>>>>>> to the git, which as far as I can tell does exactly what your >>>>>>>>>>> sum_duplicate flag does. It searches the matrix for an (i,j) >>>>>>>>>>> element, >>>>>>>>>>> and if found returns a pointer. If not found a null pointer is >>>>>>>>>>> returned. >>>>>>>>>>> This makes it easy for the user to modify A(i,j) after it has been >>>>>>>>>>> added >>>>>>>>>>> to the matrix. Are you thinking of something else? Can you point me >>>>>>>>>>> to >>>>>>>>>>> the Eigen routine? >>>>>>>>>>> >>>>>>>>>> What I meant is to have the equivalent of gsl_spmatrix_compress, >>>>>>>>>> with the difference that gsl_spmatrix_ptr is used instead of >>>>>>>>>> gsl_spmatrix_set, >>>>>>>>>> so has to build the compressed matrix from triplets, summing the >>>>>>>>>> duplicates, instead of replacing them. >>>>>>>>>> This is what is done here : >>>>>>>>>> The >>>>>>>>>> http://eigen.tuxfamily.org/dox/classEigen_1_1SparseMatrix.html#a5bcf3187e372ff7cea1e8f61152ae49b >>>>>>>>>> >>>>>>>>>> Best, >>>>>>>>>> Alexis >>>>>>>>> I'm not sure why a user would ever need to do this. The whole point of >>>>>>>>> the binary tree structure in the triplet storage is to efficiently >>>>>>>>> find >>>>>>>>> duplicate entries, so that if a user tries to call gsl_spmatrix_set on >>>>>>>>> an element which is already been previously set, it can find that >>>>>>>>> element with a binary search (rather than linearly searching the >>>>>>>>> arrays) >>>>>>>>> and change the value of that element. >>>>>>>>> >>>>>>>>> Therefore, the way the triplet storage is designed, there is will >>>>>>>>> never >>>>>>>>> be a duplicate element in the triplet arrays. All of the (i[n],j[n]) >>>>>>>>> will be unique for each n <= nz. >>>>>>>>> >>>>>>>>> Am I missing something? >>>>>>>>> >>>>>>>>> Patrick >>>>>> -- >>>>>> Alexis Tantet >>>>> >>> > >