Nash - Scientific Computing with PCs (523165), страница 50
Текст из файла (страница 50)
If applicant is an A, and R2 > P(Job|A), then reject applicant; otherwise hire applicant.b. If applicant is a B, and R2 > P(Job|B), then reject applicant; otherwise hire applicant.The distribution of outcomes can only be obtained after conducting a number of trials. For each set ofinput parameters of interest we will conduct M trials.
M should be large enough to draw a sufficientlyprecise picture of the distribution. Note that we can conduct several experiments, look at the results, thencarry out some more simulations and aggregate the results with the first set. Indeed, much of theprogramming effort in simulation is to keep results in a form that allows its later use, even if the exactmanner of use is not known in advance. There are techniques for reducing the size of M in simulationsFigure 17.3.1Events and their relationship in the hiring process as idealized by our assumptions.17: SIMULATING A HIRING PROCESS147(Hammersley and Handscomb, 1964). Here, however, we will only use direct simulation. More advancedtechniques are needed when adequate approximations to desired results cannot be obtained quicklyenough.17.4 Programs or PackagesWith the formulation and methods now settled, we can implement our simulation.
A decade ago, suchcomputations were performed in an early Microsoft BASIC on an Osborne 1 computer, and even thoughvarious simulation packages exist, we believe that ordinary programming languages are still astraightforward choice for performing the simulation calculations. We used Turbo Pascal for the examplesbelow. A technical concern may be the quality of the built-in random number generator. We could useother routines (e.g., that of Wichmann and Hill, 1987). In programming the simulation itself, the programmay not do what we intend because there is no natural cross-checking mechanism, so it is easy to codea different set of rules from that intended.17.5 Some SolutionsFigure 17.5.1 presents the distributions of numbers of successful A and B job-seekers when there are 4 jobsopen. A’s form 30% of the population, but have a 4 to 1 better "luck" in getting hired.
The averageprobability of being hired is 20%. The figure shows that the "discrimination" in favor of the A’s gives themnumerical dominance in the people eventually hired. We used M = 1000, that is 1000 trials, which gavean execution time of about 10 seconds on our 33 MHz PC. We used the random-number generator internalto Turbo Pascal in our calculations.Figure 17.5.2 presents the distributions of applicants from each group and in total. Here we see that thebulk of the distribution of the A’s is to the left. This implies that there are fewer A’s trying for the jobsbecause they have a greater chance of filling them.An aspect of the implementation that is important is that our simulation program generates a datasetready for use by the statistical package Stata so that we could easily draw the figures.
We have usedStata’s capability of drawing spline curves through sets of points in Figure 17.5.2 to bring out the visualaspects of the distribution. We believe that a major difficulty in using simulation is the choice anddevelopment of suitable techniques for displaying results in a convenient yet informative way. Suchreporting tools are a help in verifying the correctness of the simulation code and in learning about thesystem under study.In checking our simulation program, we found it useful to compute the Pascal distribution.
That is, wecalculated the probability there would be x applicants for n jobs when the probability an individualcandidate is successful is P(J). Setting d=1 (i.e., A and B candidates have equal chances) allows a checkon the simulator to be carried out using a goodness-of-fit test.17.6 AssessmentClearly the simulation task is as large as we wish to make it. Here we shall be content with the briefdescription so far presented as a sample of the type of study that may be carried out with a PC.148Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr. Dobb’s JournalFigure 17.5.1Distributions of successful A and B candidates when 4 jobs are available, A’s make up30% of the population but have a 4:1 better chance of being hired than B’s, and theaverage success rate is 20%.Figure 17.5.2Distributions of applicants (total, A and B) when 4 jobs are available, A’s make up 30%of the population but have a 4:1 better chance of being hired than B’s, and the averagesuccess rate is 20%.Previous Home Next18: EFFICIENCY STUDY — CHOLESKY DECOMPOSITIONS149Chapter 18A Program Efficiency Study:the Cholesky Decomposition18.118.218.318.418.518.618.7Purpose of the studyThe programs and systems comparedMeasuring the differencesProgram sizes and compiler optionsTime differences from program alternativesCompiler and arithmetic influencesProcessor and configuration time differencesIn this chapter we conduct a study of the performance of three variants of a single algorithm asprogrammed in several programming languages.
A variety of language translators and several computingplatforms are used. The variability of computing times and storage requirements to carry out the samecomputation is surprising. We will repeat this point for emphasis — the computations are equivalent.Minor organizational changes in the algorithms make demonstrably important differences in the resultingprograms and their performance.18.1 Purpose of the StudyThis performance study serves as a warning that claims about the relative efficiency of algorithms shouldbe suspect until proven by tests.
We follow recommendations made in earlier chapters that results andperformance of programs be verified on the target machine. This is particularly important when aprogram is to be used heavily or in a situation where erroneous results have an unacceptable cost.In what follows we will use three slightly different organizations of the same computational algorithm.The example we use is the Cholesky decomposition, and the three algorithms perform essentially the samecomputational operations on the matrix elements.
The differences in the algorithms are mainly in the waythe matrix indices are developed. Beyond the algorithmic differences we shall look at:•Differences across programming languages;•Differences between compilers or interpreters for a single language;•Differences across arithmetic libraries and compiler options within a single compiler;•Differences across computing platforms;•The effects of special hardware, in particular, numeric co-processors•Timing effects of operational choices, such as the (active) presence of communications facilities orscreen blanking programs in the PC.Along the way, we will note some annoying "glitches" we encountered in carrying out the timings andevaluations.The main points to be be learned from these Cholesky timings are:•Programming style has a large effect on execution timing and program size.150Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaSCIENTIFIC COMPUTING WITH PCsCopy for:Dr.
Dobb’s Journal•Intuitive ideas of program changes that may speed execution can be incorrect. Experience in onecomputing environment may not carry over to another.•Actual timings must be carried out whenever changes are made in the code or computingenvironment if effects on execution time could be important.The methods in this study are useful whenever performance becomes critical. For example, the Choleskydecomposition is commonly employed inside many algorithms in optimization and data approximation.If such calculations are required in a real-time or otherwise time-critical application, performancemeasurement will likely be necessary.18.2The Programs and Systems ComparedThe Cholesky decomposition of a symmetric positive definite matrix A computes a lower triangular factorL such that(18.2.1)A = L LTThis decomposition can be organized in many ways.
Two of the present codes develop the elements ofL row by row (row-wise organization), but it is just as simple to develop columnwise variants, and ourthird code is an example. We will outline the computations briefly to show that they are really quitestraightforward, which underlines why the variety of results is so surprising.First, we note that Equation 18.2.1 can be rewritten in terms of the individual matrix elements, that is,(18.2.2)Aijwhere we have already taken account of the transposition of L in the product. The key point to note isthat the summation, because of the triangular structure of the matrices, only comprises min(i,j) terms.Thus we can immediately find(18.2.3)A11 = L112The 1,1 element of L is defined as the square root of the corresponding element of A.
(The positivedefinite property of A ensures that this is possible.) Now that L11 is known, we can find all the otherelements in column 1 of L from(18.2.4)Ai1 = Li1 L11which is a direct result of Equation 18.2.2. If we use Equation 18.2.4 immediately in our program to storethe elements Li1, a column-wise organization of the decomposition results. In the row-wise variants of thealgorithm, however, we will use Equation 18.2.4 to compute L21 only.
Once this element is computed, wethen use Equation 18.2.2 to get(18.2.5)L222 = A22 - L212Again, because A is positive-definite, this is always possible. To guard against the possibility thatrounding errors or inappropriate input render the computed matrix A indefinite, we perform a test thatthe right hand side of Equation 18.2.5 is positive before taking the square root. If the test fails, then thedecomposition has also failed; our codes should report this.The process of developing L from A proceeds row by row in this organization. Algorithmically, there aresome very important considerations that we should note.
First, the elements of A are not needed once thecorresponding elements of L are computed. Second, because A is symmetric, only a lower triangle of itneed be stored. Third, a triangular matrix structure is not provided by any common programminglanguage, so it is more convenient to store A and L in a single vector of elements. If A and L are of order18: EFFICIENCY STUDY — CHOLESKY DECOMPOSITIONS151n, then the storage vector needed for our program is of length n*(n+1)/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
