# accsum Commit Details

Date: 2011-05-30 23:16:17 (7 years 7 months ago) Michael Baudin 24 23 * Fixed accsum_fdcs. * Fixed help page of accsum_fdcs for ordering of input data. * Created overview and quick start.

## File differences

help/en_US/accsum_dcs.xml
 47 47 48 48 49 49 50 51 52 50 53 51 54 52 55 ... ... 61 64 62 65 63 66 67 64 68 65 69 66 70
 ␊ A Doubly Self Compensated Sum algorithm.␊ Uses accsum_fasttwosum.␊ The input data x must be ordered in decreasing magnitude.␊ To do this, we may use the accsum_order␊ function with order=5.␊ ␊ [s,e] = accsum_dcs ( [1 2] ) // 3␊ x = accsum_wilkinson(10); size(x,"*")␊ s = sum(x)␊ x = accsum_order ( x , 5 );␊ [s,e] = accsum_dcs ( x )␊ [s,e] = accsum_dcs ( x )␊ ␊
help/en_US/pseudomacros/accsum_fdcs.sci
 23 23 24 24 25 25 26 27 28 26 29 27 30 28 31 ... ... 31 34 32 35 33 36 37 34 38 35 39 36 40
 // A Doubly Self Compensated Sum algorithm.␊ // Uses the fasttwosum algorithm.␊ // This is a fast implementation, based on compiled source code.␊ // The input data x must be ordered in decreasing magnitude. ␊ // To do this, we may use the accsum_order ␊ // function with order=5.␊ // ␊ // Examples␊ // s = accsum_fdcs ( [2 1] ) // 3␊ // s = accsum_fdcs ( [1 2] ) // 3␊ // x = accsum_wilkinson(10); size(x,"*")␊ // s = sum(x)␊ // x = accsum_order ( x , 5 );␊ // s = accsum_fdcs ( x )␊ // s = accsum_fdcs ( x )␊ //␊
help/en_US/accsum_fdcs.xml
 48 48 49 49 50 50 51 52 53 51 54 52 55 53 56 ... ... 62 65 63 66 64 67 68 65 69 66 70 67 71
 A Doubly Self Compensated Sum algorithm.␊ Uses the fasttwosum algorithm.␊ This is a fast implementation, based on compiled source code.␊ The input data x must be ordered in decreasing magnitude.␊ To do this, we may use the accsum_order␊ function with order=5.␊ ␊ ␊ s = accsum_fdcs ( [1 2] ) // 3␊ x = accsum_wilkinson(10); size(x,"*")␊ s = sum(x)␊ x = accsum_order ( x , 5 );␊ s = accsum_fdcs ( x )␊ s = accsum_fdcs ( x )␊ ␊
help/en_US/accsum_0overview.xml
 31 31 32 32 33 33 34 35 34 35 36 37 38 36 39 40 37 41 38 39 40 41 42 42 43 44 45 46 47 48 49 50 51 52 53 43 54 44 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 45 94 46 95 47 96 48 97 49 98 50 99 51 52 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 53 120 54 55 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 56 143 57 144 58 145 59 60 61 62 146 63 147 64 148 ... ... 96 180 97 181 98 182 183 184 185 99 186 100 187 101 188
 Purpose␍␊ ␍␊ ␍␊ This is a DRAFT.␍␊ ␉␍␊ The goal of this toolbox is to provide accurate algorithms to ␍␊ compute sums.␍␊ We consider here sums of a given dataset x, that is, we ␍␊ consider s = x(1)+x(2)+...+x(n).␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␉In 1993, the Book "Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods"␍␊ ␉was published. ␍␊ ␉Associated source codes in the Matlab language were provided at http://www.netlib.org/templates/. ␍␊ ␉From 2000 to 2011, these function have been ported to Scilab 4 by Aladin Group (IRISA-INRIA).␍␊ ␉Starting in 2010, Michael Baudin upgraded this module to Scilab 5.␍␊ These algorithms may be required to manage datasets which ␍␊ are ill-conditionned with respect to the sum function, which ␍␊ happens when the data are varying highly in magnitude and in ␍␊ sign. ␍␊ Hence, these datasets are very sensitive to small changes in the ␍␊ input. ␍␊ In this case, the "sum" function of Scilab is not appropriate ␍␊ and may produce results which have only a small number of significant ␍␊ digits, or no significant digit at all. ␍␊ Users may consider the condnum module and the condnb_sumcond ␍␊ function to compute the condition number of a particular sum. ␍␊ See http://atoms.scilab.org/toolboxes/condnb for details.␍␊ ␍␊ ␍␊ ␍␊ The module is mainly based on the book "Stability and numerical ␍␊ accuracy of algorithms" by Nicolas Higham.␍␊ ␍␊ ␍␊ ␍␊ In order to test the algorithms on practical datasets, ␍␊ we include a dataset which was created by Yun Helen He and Chris H.Q. Ding. ␍␊ This dataset is provided in the "demos" directory, in the "etaana.dat" file.␍␊ ␍␊ ␍␊ ␍␊ "The SSH variable is a two-dimensional see surface volume (integrated ␍␊ sea surface area times sea surface height) distributed among multiple ␍␊ processors. ␍␊ At each time step, the global summation of the sea surface ␍␊ volume of each model grid is needed in order to calculate the ␍␊ average sea surface height. ␍␊ The absolute value of the data itself is very large (in the order of ␍␊ 10^10 to 10^15), with different signs, while the result of the ␍␊ global summation is only of order of 1. ␍␊ Running the model in double precision with different number of ␍␊ processors generate very different global summations, ranging from ␍␊ -100 to 100, making the simulation results totally meaningless.␍␊ [...]␍␊ The 2D array is dimensioned as ssh(120,64), with a total of 7860 ␍␊ double precision numbers."␍␊ ␍␊ ␍␊ ␍␊ Other datasets are provided in this module, based on examples ␍␊ created by Wilkinson, Higham and Priest.␍␊ ␍␊ ␍␊ ␍␊ ␉The toolbox is based on macros and compiled source code.␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ Authors␍␊ Quick start␍␊ ␍␊ ␍␊ ␉1993 - Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June M. Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, and Henk Van der Vorst␍␊ ␉␍␊ The accsum_fdcs function ␍␊ provides a doubly self compensated sum algorithm. ␍␊ The data must be ordered in decreasing magnitude. ␍␊ To do this, we use the accsum_order ␍␊ function with order=5.␍␊ This function is based on compiled source code, so that it is ␍␊ fast enough, even for relatively large datasets. ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␉1993 - Univ. of Tennessee and Oak Ridge National Laboratory␍␊ ␉␍␊ The accsum_fcompsum, which uses ␍␊ a compensated summation algorithm.␍␊ It does not require an ordered input and requires ␍␊ less floating point operations. ␍␊ In the current case, the simply compensated summation ␍␊ algorithm does not perform sufficiently well.␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␍␊ Authors␍␊ ␍␊ ␍␊ ␉2000 - 2001 - INRIA - Aladin Group␍␊ ␉2011 - DIGITEO - Michael Baudin␍␊ ␉␍␊ ␍␊ ␉2010 - 2011 - DIGITEO - Michael Baudin␍␊ ␉␍␊ ␍␊ ␍␊ ␍␊ ␍␊ ␉"On properties of floating point arithmetics: numerical stability and the cost of accurate computations", Douglas Priest, 1992␍␊ ␉␍␊ ␍␊ ␉"Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications". Yun He and Chris H.Q. Ding. Journal of Supercomputing, Vol.18, Issue 3, 259-277, March 2001. Also Proceedings of International Conference on Supercomputing (ICS'00), May 2000, 225-234.␍␊ ␉␍␊ ␍␊ ␍␊ ␍␊
etc/accsum.start
 61 61 62 62 63 63 64 64 65 65 66 66 67 67 68
 // ====================================================================␊ // A Welcome message.␊ ␊ mprintf("\tType ""demo_gui()"" and search for ""%s"" for Demonstrations.\n",modulename);␊ mprintf("\tType ""help accsum_overview"" for quick start.\n");␊ //mprintf("\tType ""demo_gui()"" and search for ""%s"" for Demonstrations.\n",modulename);␊ ␊ // =============================================================================␊ // Create variables at level #0␊
 5 5 6 6 7 7 8 9 8 10 9 11 12 13 14 15 16 17 18 19 20 21 22 10 23 24 25 26 27 28 29 11 30 31 32 33 34 35 36 37 12 38 13 39 14 40 ... ... 45 71 46 72 47 73 48 49 50 51 52 53 54 74 55 75 56 76 ... ... 80 100 81 101 82 102 103 83 104 105
 ␊ The goal of this toolbox is to provide accurate algorithms to ␊ compute sums.␊ We consider here sums of a given dataset x, that is, we ␊ consider s = x(1)+x(2)+...+x(n).␊ ␊ The toolbox is based on macros.␊ These algorithms may be required to manage datasets which ␊ are ill-conditionned with respect to the sum function, which ␊ happens when the data are varying highly in magnitude and in ␊ sign. ␊ Hence, these datasets are very sensitive to small changes in the ␊ input. ␊ In this case, the "sum" function of Scilab is not appropriate ␊ and may produce results which have only a small number of significant ␊ digits, or no significant digit at all. ␊ Users may consider the condnum module and the condnb_sumcond ␊ function to compute the condition number of a particular sum. ␊ See http://atoms.scilab.org/toolboxes/condnb for details.␊ ␊ The flagship of this module is the accsum_fdcs function, which ␊ provides a doubly self compensated sum algorithm. ␊ This function is based on compiled source code, so that it is ␊ fast enough, even for relatively large datasets. ␊ The data must be ordered in decreasing magnitude. ␊ To do this, we may use the accsum_order function with order=5.␊ ␊ The module is mainly based on the book "Stability and numerical ␊ accuracy of algorithms" by Nicolas Higham.␊ ␊ The toolbox is based on macros and compiled source code.␊ ␊ Type "help accsum_overview" for quick start.␊ ␊ Features␊ --------␊ ␊ * This modules depends on the helptbx module.␊ * This modules depends on the apifun module.␊ ␊ TODO␊ ----␊ ␊ * Implement pairwise summation.␊ * Implement optimal summation.␊ ␊ Author␊ ------␊ ␊ * https://hpcrd.lbl.gov/SCG/ocean/NRS/ECMWF/img14.htm␊ * https://hpcrd.lbl.gov/SCG/ocean/NRS/SCSsum.F␊ * "On properties of floating point arithmetics: numerical stability and the cost of accurate computations", Douglas Priest, 1992␊ * "Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications". Yun He and Chris H.Q. Ding. Journal of Supercomputing, Vol.18, Issue 3, 259-277, March 2001. Also Proceedings of International Conference on Supercomputing (ICS'00), May 2000, 225-234.␊ ␊ ␊
macros/accsum_dcs.sci
 22 22 23 23 24 24 25 26 27 25 28 26 29 27 30 ... ... 30 33 31 34 32 35 36 33 37 34 38 35 39
 // Description␊ // A Doubly Self Compensated Sum algorithm.␊ // Uses accsum_fasttwosum.␊ // The input data x must be ordered in decreasing magnitude. ␊ // To do this, we may use the accsum_order ␊ // function with order=5.␊ // ␊ // Examples␊ // [s,e] = accsum_dcs ( [2 1] ) // 3␊ // [s,e] = accsum_dcs ( [1 2] ) // 3␊ // x = accsum_wilkinson(10); size(x,"*")␊ // s = sum(x)␊ // x = accsum_order ( x , 5 );␊ // [s,e] = accsum_dcs ( x )␊ // [s,e] = accsum_dcs ( x )␊ //␊
changelog.txt
 11 11 12 12 13 13 14 14 15 16 15 17
 * Used consistently apifun.␊ * Created missing .ref␊ * Created higham example.␊ -- Michael Baudin March 2011␊ * Fixed accsum_fdcs.␊ * Fixed help page of accsum_fdcs for ordering of input data.␊ * Created overview and quick start. ␊ ␊