From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 111549 invoked by alias); 7 Feb 2016 21:34:31 -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 111527 invoked by uid 89); 7 Feb 2016 21:34:30 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 spammy=H*r:sk:na01-bl, H*r:65.55.169, H*r:sk:mail-bl, Best X-HELO: na01-bl2-obe.outbound.protection.outlook.com Received: from mail-bl2on0106.outbound.protection.outlook.com (HELO na01-bl2-obe.outbound.protection.outlook.com) (65.55.169.106) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA256 encrypted) ESMTPS; Sun, 07 Feb 2016 21:34:28 +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 BN3PR0301MB0897.namprd03.prod.outlook.com (10.160.156.14) with Microsoft SMTP Server (TLS) id 15.1.403.16; Sun, 7 Feb 2016 21:34:24 +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> CC: "gsl-discuss@sourceware.org" From: Patrick Alken Message-ID: <56B7B85C.10508@colorado.edu> Date: Sun, 07 Feb 2016 21:34:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.4.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit X-ClientProxiedBy: DM2PR09CA0013.namprd09.prod.outlook.com (25.160.127.23) To BN3PR0301MB0897.namprd03.prod.outlook.com (25.160.156.14) X-MS-Office365-Filtering-Correlation-Id: 883e7e98-31d9-49cd-3a9e-08d33006731f X-Microsoft-Exchange-Diagnostics: 1;BN3PR0301MB0897;2:DlETr7bCwjibFiGIZRhz2ETcSyXuv8AEBNKHQL9OuAFmkHFm8adRFOK7ZNuEXCIeSzv8BUBVyCkYKbF73Ymuum6AiYv4MQRum98Wpp7Cab2OweJoNeqIeO2I2sxi8RmMlNJZ4vQsX/ZeqelAir+0xFe8VR9/gtsRV7Ane+to3C9AN1kSw4PUbHMBvSpU4rnZ;3:YwMAwRZoR1U2GJUT9pvLfO3F+mDeGPfERSLM7qsXl5k6np4oCIA8Y7R6YWlbSYBL8ZFhQgDw4kTYtmbskHlqSFRDM8zZjhGIVEgoV3ZV08JB6UNoN3oa0xtD2KGS1IK5;25:Dms9x1T012M22Ez3cTrPNv+6KMRAZPFIXqC/G9FVKi1A1Z6nK7+vbA1uIHN3lcJfWVHm0auhvWvWGlW10oa8mQuKlAxMokYuz7mNtUB011FOkmWKROvdamSH/L92MGbaHkpJzYXOT/HHo1JNnC8TDqIk87rW+2GFHXPZVBSza/FYlI/eNBlxPeut4WhtxqA+KJ6hFKWHYMYW1t1TRz6Zb6Qxl03kANbwMSsWwHYK4jVdoBFG4u2exsRCFlQSeuggGp0UzaaPbIAEsiiv5dvHFWsoFMvQFlQ9ai2AhV2LYIrrAVhCx17Bxr4UvTrcHNjx X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN3PR0301MB0897; X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001);SRVR:BN3PR0301MB0897;BCL:0;PCL:0;RULEID:;SRVR:BN3PR0301MB0897; X-Microsoft-Exchange-Diagnostics: 1;BN3PR0301MB0897;4:ArQTwyW0lLks3ZObqKEiA11F3keUqCJPNZ9KEv9RQQ9tIzeWXEOjuA90oZsndXaILFrUPku+0bYS+5J/gIeLumidOxs9Mbkqk/aoZL4O6dmxB6VV+3DeUM+LnaDCA4hQicwLmUpQIcKn8y2Id8GqKgTpJ5P2jnnSSMBD92za/TtXg/3XQtSckqR7mVu7HsG+zUUn9C5eglJ9YtViUUGNhW+zIWzvZQRyqFkQqezMA85BTPlP+H5hHxr0YLA8tX5KSD7x3juoltzacNqMSoNvOgGLukz+rq9lEGy3g9upc5IHXVKNSug4MOK0RqjlCuk8njbutGVdx4ckvbi0i/CLSqVtPFEJEfsxk8cd5toZGkh04OgxSJwzZDjZIkOiOjrr X-Forefront-PRVS: 08457955C4 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(6049001)(6009001)(24454002)(479174004)(377454003)(5001960100002)(47776003)(19580405001)(2950100001)(5004730100002)(75432002)(4001350100001)(65816999)(40100003)(33656002)(122386002)(50986999)(5008740100001)(77096005)(15975445007)(117156001)(90282001)(42186005)(89122001)(189998001)(50466002)(110136002)(3480700003)(1096002)(586003)(4326007)(19580395003)(23676002)(65806001)(83506001)(66066001)(92566002)(64126003)(230700001)(36756003)(88552002)(93886004)(54356999)(2906002)(3846002)(76176999)(87976001)(65956001);DIR:OUT;SFP:1102;SCL:1;SRVR:BN3PR0301MB0897;H:[192.168.0.75];FPR:;SPF:None;MLV:sfv;LANG:en; X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCTjNQUjAzMDFNQjA4OTc7MjM6SXZRUGhBbG5Pa3ExWnlFY2J2dHM1YmtU?= =?utf-8?B?ZUsxL1lsOStBL010SGYxcStiOE9jcituR0pKUHFCcGxGQ29OU1pQWWM0RGh5?= =?utf-8?B?U0FUQlE4dnc5M3Z4M3M2bERGR2ZDT2QzQzVjYjBJbFBWaExkVHc4SUJUTyt6?= =?utf-8?B?TXA3b0FCUndTdW1WOEREWkJzbndNZUxGOGxSN04vT3Ird2RJYzhTZGt1c093?= =?utf-8?B?QnNDSnhVYjRxbDYyS1RSaWVnR29WemRZQjZ4SkNxM3h0WjZPbjlXSHlVN1ZE?= =?utf-8?B?VVAwamJnZEg5aWY2cXJtVXNCRDV4Y0g0L3pZYi85aExtT1Y3MTdRTTJFUFVq?= =?utf-8?B?dldFRjBvU0ExS081UlNDcis3TFZSM1oxd3BMakQyUVV2U2VvYlM0MG9SdXJ5?= =?utf-8?B?bW94ZDlDOTdIa2czMVJOSHBmOEQ5b1dicnpMZk9obU9ZMzIvR1NzUnNVV1VZ?= =?utf-8?B?cVlLQnNraFZOUkx6bnZ5NzF2T3R5U0lmTFRPSVk4OTlVamFhVE5ZK3ZMT2Yz?= =?utf-8?B?OVp0a2JCYVVWcDFqVnZoZW5aajNBQzNFWUdBdy91YmJOZWRSbWYyVXNRNVRX?= =?utf-8?B?d2hic0dGT0UveEtzVE1EN0V5RFd1Rm40UEVkam9PemFWK2pRN2F2Mnp6UjN5?= =?utf-8?B?ZVUzbklmeVRjVmdLQnhMRmZiRzJqdHNLTW9na3RYNWJSZ0hRRDF6TkM5ck9T?= =?utf-8?B?T3lncDdiNEZDLzY1WkRMNmc5c2RwWkhHWS9ZZVpRSi9HdUltellibDdVeEVh?= =?utf-8?B?RU8ydUZsR25tTHYyWUtBRzUvUHZWT3VIZzVPR3RNMUI4cTJIT0lHK0FUWGV5?= =?utf-8?B?WHdhT1haQ1EvdUdpbmpnVFcwVmdDNWphK2RtVVBTUjFqa2lrMy9oRk1mQ0VB?= =?utf-8?B?NStMeWdJTlVxaTJqM1lMNmxHZlFZUFZwN1FaODhQVEUrUlgwQ24vNy9rWUJu?= =?utf-8?B?MkhpSy80L0dtWWNOaFljVkNka3NFKzJMNlQvM1c0dmtBNlg0VzlUTWxUb3ZK?= =?utf-8?B?eW0vNU9EcmJhV0FqUUIvTHZ3cEFROWJhZjBOWVpwL2VtNnd3MEhMM1hLVXhl?= =?utf-8?B?Q0VnRHpaS0NuaEVQcEU3V2pFb052N2xqNTZXVWJjWEgrNnlzUis3Q05kaXBW?= =?utf-8?B?SjVJc3BiTW9HVXdxaG1XdGxnZW5LMzVwaEErM3BURzhJZER6YTZoRk0rMzcw?= =?utf-8?B?UUVBR0hObUR2bU5kK09yMDhwd3hPTVlGOWVSM3lCU3NEbkJRcEtpYklHbTNa?= =?utf-8?B?TnZiVXhzeTIvTmMwMkhWRk5YSlc2eSthYlBWWVpiVEFabVlLRm9aWVZXU0pN?= =?utf-8?B?eXB2eG9jQ0J3WEhBZS96TlJjTUlvbkJCbStCYlBlbFRRL0pSL0N0MVByNWxr?= =?utf-8?B?eHI2VER4T3owYlZiUVR1VE5qUk40d0gxcm9nYXVqNlJpUm9Sa01XNUFDZ3U0?= =?utf-8?B?ckRUek5maDdoazd6TUh2UzFKV3JZZVpnN1BqWlZMRDEvWmdoZzBlRmNSSEcv?= =?utf-8?B?RndwVkVqWExmYTJ3SFgrV05vZXlQMnFrR0wvMmVJU21OaUxlRW1kK2ZYZWND?= =?utf-8?B?SFBMeHZjeDlSZy9IQzBzYmx3Z3B3blFYS21pRmIvS29UdnptWktQM0o4MHI1?= =?utf-8?B?dWpDL2Zia2ZiZkMxWTR4SERYOVJ2TjdnWnc5eHgvQ2xLbmZNc2VCeHdxOVh6?= =?utf-8?Q?HIn7xnjPtioDxnnfoMn8=3D?= X-Microsoft-Exchange-Diagnostics: 1;BN3PR0301MB0897;5:PtaZ5lxSUiK2dasqIkrWGbqjgLClC01aOFacvnlWwYH4M5bnNSiTxQPTdAOOlLUigwJPvJaPi0iNAV+O8c5iiBFbiGeCEj5IF2H/jxmTeEDJL5oxYhvUsb/hwJeKVA3i7s1V0sPFr0j1A7oOrDK61g==;24:Sw2A6PI3oSXTqDvDweyyXzr6BDcEVaFMFIQdRlqOVqQHGBSd79R8jI2EY7AXAoLP0tqSF10gzbFpwI3YDT0yCGss0k2D4W+aLbFY2tAlFQo= SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: colorado.edu X-MS-Exchange-CrossTenant-OriginalArrivalTime: 07 Feb 2016 21:34:24.4047 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN3PR0301MB0897 X-SW-Source: 2016-q1/txt/msg00011.txt.bz2 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 > >