From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 105915 invoked by alias); 9 Nov 2015 22:16:35 -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 105906 invoked by uid 89); 9 Nov 2015 22:16:34 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.6 required=5.0 tests=AWL,BAYES_50,RCVD_IN_DNSWL_NONE,SPF_HELO_PASS,SPF_PASS autolearn=ham version=3.3.2 X-HELO: na01-bn1-obe.outbound.protection.outlook.com Received: from mail-bn1on0147.outbound.protection.outlook.com (HELO na01-bn1-obe.outbound.protection.outlook.com) (157.56.110.147) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-SHA256 encrypted) ESMTPS; Mon, 09 Nov 2015 22:16:33 +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 BY1PR0301MB0901.namprd03.prod.outlook.com (10.160.195.140) with Microsoft SMTP Server (TLS) id 15.1.312.18; Mon, 9 Nov 2015 22:16:29 +0000 To: "gsl-discuss@sourceware.org" From: Patrick Alken Subject: Large linear least squares Message-ID: <56411B37.2050504@colorado.edu> Date: Mon, 09 Nov 2015 22:16:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8"; format=flowed Content-Transfer-Encoding: 7bit X-ClientProxiedBy: DM3PR18CA0006.namprd18.prod.outlook.com (25.164.243.16) To BY1PR0301MB0901.namprd03.prod.outlook.com (25.160.195.140) X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0901;2:x1B2SOVsmmUdBUwR9xRWKx9hbSC4ghr2TI+0hd50uABdZrNl8vURATVc6G4OYm0t+QRG033nLJnhccxq4BIXARX2yKwQD5aRF/dE/RKHQGPPmMezAyevTOKDksMai/eRpnEdlOXDxtbUWy4WG+kMoskP9Q4aiq5wXxMDbrG4oAw=;3:/AwhEGA0jSepzhyS1FUInW7vbCYIWAJd0+ZuhmcPq/dE3cMaTq4cNZrJxbp2DpZJun5XB2JiuLV+UHezCC0Vm3WTM07Uhn9otn08sSfOqcfgzQ2cPYL3oLouyLT29EHpjEHKdhKqKSEJygg/w7UIhg==;25:+uyH/nTTZ1UZZv4xr786tdPVFxXFl4SO6+h1H5xcWoTlV+dqEYBLKshzfBU7O8dEwLonjc9ZOAvIQhLFCZSOtjOMolbd7WnoggbZKfmyghyEFuwSSeidH2RURulfsV1nZilJ/dGmMy0EuFYSaZCOwKH8+nh93cOdsgkB+IlF+CpOXt1d51EuSNlPQlUv1c6hHhpRDj5nfzzRYKrwOIxLr/erQdVs3+bCyh+PeT6DAyCaI+HUtXRm2uvp55HAXe165Q9A8Cev3kQhysZqrKRubg== X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BY1PR0301MB0901; X-Microsoft-Antispam-PRVS: X-Exchange-Antispam-Report-Test: UriScan:; X-Exchange-Antispam-Report-CFA-Test: BCL:0;PCL:0;RULEID:(601004)(2401047)(5005006)(520078)(8121501046)(3002001)(10201501046);SRVR:BY1PR0301MB0901;BCL:0;PCL:0;RULEID:;SRVR:BY1PR0301MB0901; X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0901;4:naLNLejpcHPOd2obD2TRcEDWX9lzH1HVo/XcP/u+HbJfT7iknmYWvo9/Y1AL/2ORjIDaI12DJJ+hvCUTe1++FJFWoD7eP+AHeg2qysudrRmechl/nEOtEcvclAttObQluw6t9r445vWhpdB3JmI615zgphR3+0/bzT4Trvf5zz4QvheTcJp3LZqGFfEAggnWtVzL8vSW7+uKAjnzSo+9mRgA+1f25rlIayt10p+J8xJW9m6q81U46zHGi4ReZxcsARsQGSfyK+m4brE+GeX8D91/rCEIr4ku4DDR7GFXha1BWFs7UtQqdHdzjeli/aoU//z6DsGhuDH26vpd46F1zmIJSUEbYNlkeBb8BBqAd2s4VsMXHl2mFDhDi2zo8EMB X-Forefront-PRVS: 0755F54DD9 X-Forefront-Antispam-Report: SFV:NSPM;SFS:(10019020)(6009001)(189002)(199003)(164054003)(53754006)(450100001)(5001960100002)(107886002)(89122001)(110136002)(5008740100001)(87266999)(50986999)(189998001)(54356999)(87976001)(47776003)(2501003)(40100003)(101416001)(65816999)(65956001)(66066001)(33656002)(50466002)(230700001)(64126003)(229853001)(65806001)(105586002)(99136001)(83506001)(59896002)(122386002)(90282001)(92566002)(88552001)(75432002)(23676002)(36756003)(5007970100001)(42186005)(77096005)(106356001)(5001920100001)(97736004)(80316001)(4001350100001)(81156007)(2351001)(5004730100002)(140573001);DIR:OUT;SFP:1102;SCL:1;SRVR:BY1PR0301MB0901;H:palken-co-ll.ngdc.noaa.gov;FPR:;SPF:None;PTR:InfoNoRecords;MX:1;A:1;LANG:en; Received-SPF: None (protection.outlook.com: colorado.edu does not designate permitted sender hosts) X-Microsoft-Exchange-Diagnostics: =?utf-8?B?MTtCWTFQUjAzMDFNQjA5MDE7MjM6OU1xRERRMmUrVDVhM3I5RUhLVFh2ZWE3?= =?utf-8?B?NEgxdGlRckxvWGtBSzY1aTZVK2l0ZHRYbzBlaGxDT1N5bTBTbXBidVJyU2x4?= =?utf-8?B?ajNDaVAwOWRQSUVvcWlwd2hUR3ZMZVNWOVcvNWxrdWc0VjlocGJtRkZSeXpG?= =?utf-8?B?YjdNN2Fabk9EYUNaRmZEK0duZlRpUEs0UWRjN2NrOXFma3M0cFlXU3NyYWMr?= =?utf-8?B?dzNqaG5xNGVYOE5UOHFjKzhWRDN6Y2VwdkRUbEtFcnV5YWlBVitWZzRnSnRx?= =?utf-8?B?OXlIdy9KVmJNaGZhTUpTUm40OTY2cFBBd3o0OW02Tlg0SHpHMHZYMU9xYnZR?= =?utf-8?B?ZTFTbHpkM3RVa2NSSjVJU1QrZ1o4by9adnNVaGp2Nmd5RHY4enhzc3FWVFov?= =?utf-8?B?UVVaRzNrYWRVbW9DaFJUOWJLd2c2NEZUKzlQTlNuYStWNVFiSHBDdGVrVlZt?= =?utf-8?B?b1NWWjNXRUxLWGpHQlo4RkdXYmw4WmFHV0U3YVp1cFVTZ0E2TFlxaThSbVdN?= =?utf-8?B?WSsvbEw4YUwrYzd1WkNmYm9NT0xEWTFRRWlZQmpyT2NVM3lFSEtXK09uZHR1?= =?utf-8?B?b0hQa3pub1pka09XcTlud1Q5RnhIS01qVG5zVEtUZmNXMEdKNXdZd25oeUJl?= =?utf-8?B?WWVvZmhhNTZsdFVGYXRVSlQ4blU4Vk9LakJkbWNlSXRDU0E2WXlPVXVWUUt1?= =?utf-8?B?VGluWGd2TDZIOVlTV2NjRVJuT2pmdmt4N3dyNDRmY0VIaDAzclJzeGNCMmda?= =?utf-8?B?R2g5U1pyZ0dNbGM3b0YyWVpQczVkYVBlQVo1QVFyN211ZHhTSWtFVnZESzRI?= =?utf-8?B?WXpndFh4R0dqbXNnS3ZuUElEQm5ORGcvOTYyc3B4ZTd2ck1RVmd5TWw5QWFE?= =?utf-8?B?OGZBNDVYUWsyMUVaVUt5SGtGV2JaYno5SUlydE11QmFJeUsvTG4xV0wrNnc2?= =?utf-8?B?dldENG5IZjA4WDV4RGVuekNWSmtZQ3c4Z0ZiSEs2MXJVUGlBYStudkZWaWVa?= =?utf-8?B?UnpXeU84UjIxS3NvdzVORWQvb1FGZUJzOWxoemtqLyt1aXBtNnR4QXhIeGlX?= =?utf-8?B?TWhUQXEybUpUMGdlMkVjRW8rRlFjdEpMK00wUTNKSnplcWtDVk0yYVdvVkg4?= =?utf-8?B?VW5rK09aaXhqZUdXSSs4NWVCbmg1MThDVlgzRVgyM2toREF5L01selJHTlJD?= =?utf-8?B?YXRNYThuaVVYb21PTnFNVGRTNkRwN2dHSlVUeWFXanpLdk40RHJiOUo0dG5H?= =?utf-8?B?UEpUT3pmNmFhR2trc2Y0aTdiem5XbjZhZk5nNEp1M1BjNWVIVXhQejdpbnc0?= =?utf-8?B?aUFIUVNOVW1hdHRobW9PV3VQY0VFcnc1cHhKTTRtd1FkZitoKytlWTRWM2s2?= =?utf-8?B?NFZJOXA4S21QWDNRT2VleVJjRmk3QUE2eTZNcm9pZCthc21WZGZwajIrWE8r?= =?utf-8?B?KzkxYWJYVW5rbkpTRitLVm1VZEdCc0FhV2FubHRqcHVZb0JXY092bGg0ZU5Y?= =?utf-8?B?NzBvVlpHYjc4MUphNW5acHVnSVZtUjhOSlVLV1dvdEROa3M4RDNaR2FnQjdo?= =?utf-8?B?T3JETFJaWkNxbktWRmJTWWFCK1JUZjRKbTFnSjFsUnZQZHRUa0ZtSnRJbUlV?= =?utf-8?B?Tyt5QlZrNDZ5YUhRN3pHSk5Hak80eE9YOEYwM21hOEQzaUVCSms5Q1pWM1lM?= =?utf-8?B?N1FLdlorVTd4cjc4V2JTTVE0eitpOVdCSlRNYnlCZG52R1JBUnl2WjBuWklB?= =?utf-8?B?T3dwRDZTZnBPVU5XZmJoSGgvRkw0U0VqWnRiaWlucGRYWXB0VUlVSElKZlBz?= =?utf-8?Q?t8Zt3CZj9948nfe?= X-Microsoft-Exchange-Diagnostics: 1;BY1PR0301MB0901;5:l/J6vywzYuKbCnxqDl4SJ6tinLVjudBalEDxL2KO45e+Wn/ycVnPQCkZ17tbaN7jpZntplLiJHusMGxk56XUb6QkXWtp9uMnqaGlqU3YhuoBH8eim5HPDF38fK+l3Zk04mAdzxckaw/kFAVTOMA8/Q==;24:KvVRhsbBq0q+HhZnzgWzB/pczdwQH6JBmqxf6HnA48+FN4c5yZQTMlKV1fJm2Gr6iWyZuQ6HuvSc6Hmt/FQga9aZjJxvrIBFMXRO5YoiavQ=;20:edIIOJhJSUEHHaLly1Ek+FAj+3nBv+yvyU4IWdBQ75pCk3p8c7oCum/mohLDVRsZo+ShvnDjUgzfL3K0Uw/+wg== SpamDiagnosticOutput: 1:23 SpamDiagnosticMetadata: NSPM X-OriginatorOrg: colorado.edu X-MS-Exchange-CrossTenant-OriginalArrivalTime: 09 Nov 2015 22:16:29.7199 (UTC) X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted X-MS-Exchange-Transport-CrossTenantHeadersStamped: BY1PR0301MB0901 X-SW-Source: 2015-q4/txt/msg00007.txt.bz2 Hello all, I have implemented two solvers for large linear least squares systems in GSL. These routines are designed for so called "Tall Skinny" matrices, which have many more rows than columns. The main idea is to accumulate the matrix one block of rows at a time to avoid having to store the entire matrix in memory at once (which may not be possible depending on the size of your matrix). The first method is the normal equations method, which is well known and popular for its speed and simplicity. This method calculates and stores only the normal equations matrix X^T X which is much smaller than the full matrix X. The normal equations method is accurate when applied to well conditioned matrices, but suffers from numerical instabilities for ill-conditioned matrices. The second method is the Tall Skinny QR (TSQR) algorithm from Demmel et al, 2008. This method calculates the QR decomposition of X, updating the R factor each time a new block of rows is added to the system. Since its based on a QR decomposition, it is much more stable than the normal equations method on badly conditioned matrices, though the method is roughly twice as slow as the normal equations for n >> m. Everything is on the git and documented, with an example program. Feedback is always welcome. I am planning to push out a 2.1 release soon due to a few of the bugs reported over the last couple weeks. Thanks, Patrick