Nash - Scientific Computing with PCs (523165), страница 7
Текст из файла (страница 7)
The other (JN) prefers to keep a "to do" list using a text editor and to transfer the "to dos" toactivities with additional comments once completed. The choice is, once again, personal, and the computera possibility rather than a requirement.Previous14Copyright © 1984, 1994 J C & M M NashHomeSCIENTIFIC COMPUTING WITH PCsNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 CanadaCopy for:Dr. Dobb’s JournalChapter 3Computational capabilities of PCs3.13.23.33.43.5Good newsApplication problemsComponent computational problemsComponent symbolic problemsGetting things to workThe PCs introduced in the previous chapters have not conventionally been regarded as tools suited forserious computation.
Early PCs had limited memory and slow execution rates that are not, by choice, thecharacteristics of a number-crunching engine, especially as the processors usually lacked floating-point(REAL number) arithmetic instructions. Moreover, the programming tools were usually interpreters oflimited capability with quirks or errors in exception handling and special functions. This chapter pointsout where PCs and their software are likely to be able to carry out scientific computations.3.1Good NewsA number of technological and commercial developments have vastly improved the capabilities of PCsfor scientific computation:•The development of high-performance floating-point co-processors with well-defined properties thanksto the efforts of a number of workers, particularly W. Kahan of Berkeley, toward the IEEE FloatingPoint arithmetic standards and concurrent development of the Intel 80x87 and related devices;•Larger memory capacities and address spaces;•Faster, more efficient interfaces such as video-display adapters, memory managers and diskcontrollers;•Fast, large and inexpensive fixed disks;•More capable operating software allowing better use of available hardware, such as disk or memorycaches (Section 8.3), printer buffers (Section 11.8), and utility software (Chapter 10);•Full-feature programming language compilers;•Reliable application packages, such as modern statistical software.Interest in manipulating graphical images for video games has provided an impetus for large memoriesand fast processing.
Computers with these features are commodities like any other consumer electronicproduct. In consequence, it is now possible to buy a PC with roughly the raw processing power of atypical university central computer of a decade ago and to pay less than $5000 for it.Recognizing this computing power, developers have produced some powerful scientific software. For theuser — and the reader of this book — the issue is finding and choosing the right software at the rightprice for particular problems.
Since many scientific problems have different names or descriptions indifferent subject areas, this can be more difficult than we would like. In this chapter, and indeed in therest of the book, we will try to explain some of the jargon that is associated with various problems. Alsowe will try to point to the component sub-problems that commonly arise in many classes of scientificcomputing, since users can "put the pieces together" if they know what pieces they need.Next3: COMPUTATIONAL CAPABILITIES OF PCs15Our goal is to recognize when our machine can perform desired tasks, and if it can, whether it can do itsufficiently quickly for our needs, with acceptably low human effort involved.
We take the position thatthe central obstacle to successful scientific problem solving usually lies in one or more mathematical subtasks. There are, of course, many ancillary tasks to be performed, often requiring most of ourprogramming and management effort. These are not ignored, but they are generally not the criticalobstacle to the use of a given computer in carrying out scientific work. That is, one or more of themathematical sub-problems may prove insurmountable and prevent the use of the PC in the overallsolution of the scientific problem.3.2Application problemsScientific and technical computing clearly has more variations than we can discuss in a book of this size.However, the main types of problems can be listed. These are:•Analytic problems, that is, those involving solution of equations or finding of roots or extrema — themanipulation of existing data to extract information;•Simulation problems, where we synthesize plausible data a number of times to explore possibleoutcomes to particular situations;•Transformation or presentation problems, where we are trying to recast existing data into a new form.It is useful to recognize these three types because analytic problems are "finished" when we have asolution.
However, we decide how many sets of conditions to specify for simulations. That is, they canbe open-ended. Transformations and presentation problems may involve several cycles of experimentationto achieve a desired "view" of our data.In the next two sections we mention the names of some mathematical problems to which applicationproblems are often reduced. Much of the work of problem solving is learning how to do this efficientlyin both human and computer effort. Of course, we have afterwards to interpret the results so that theymay be understood.3.3Component computational problemsThis long section lists and briefly describes some classic problems of computational mathematics. It alsoprovides a notation we can use in later chapters.Numerical Linear Algebra — Matrix CalculationsA matrix is a rectangular array of numbers.
Within a matrix A that has dimensions m by n, that is, havingm rows and n columns, the i,j element of A occupies the row i, column j position. This simple structureof numbers forms a building block of linear algebra. It has been applied in almost all subject fields, bothdirectly or as a part of other numerical methods. The most common general problem types addressed bynumerical linear algebra are:•Linear equations, that is, finding the solution valuesxj , for j = 1, 2, . . ., n to the n equations(3.3.1)We shall generally use the matrix form of these equations(3.3.2)Ax = b16Copyright © 1984, 1994 J C & M M NashNash Information Services Inc., 1975 Bel Air Drive, Ottawa, ON K2C 0X1 Canada•Least squares approximations. Here we wish to find a set of valuessum of squaresSCIENTIFIC COMPUTING WITH PCsCopy for:Dr. Dobb’s Journalxj , j = 1, 2, .
. ., n such that the(3.3.3)is minimized, where(3.3.4)Again, this may be written in matrix form as(3.3.5)whereTdenotes matrix transposition, andr = b - Ax(3.3.6)Note that•A is now rectangular (m by n), whereas, for linear equations it was a square matrix.Matrix decompositions, including the eigenvalue decomposition. These problems aim to find productsof other matrices that are equal to the given matrix A.
The matrices that make up the decompositionhave special properties. Some particular decompositions are:· the singular value decompositionA = U S VT(3.3.7)where U is an m by n matrix of orthogonal columns such that UT U = 1n , the identity of order n, VTTis an n by n orthogonal matrix so that V V = V V = 1n, the identity of order n, and S is a diagonalmatrix having non-negative elements.· the eigenvalue problem (square matrices)AX=XE(3.3.8)whereX has some normalization and E is diagonal. For symmetric matrices whereAT = A(3.3.9)the eigenvalue problem is straightforward, but it becomes increasingly difficult when the matrix isnon-symmetric or complex.· the QR decomposition (or orthogonalization)(3.3.10)whereR is upper-triangular or right-triangular, that is(3.3.11)andA=QRRij = 0ifi>jQ is m by n orthogonal3: COMPUTATIONAL CAPABILITIES OF PCs17Q T Q = 1n(3.3.12)· the LU decomposition (A square)A=LU(3.3.13)whereL is lower-triangular and U is upper-triangular(3.3.14)Lij = 0ifj>i(3.3.15)Uij = 0ifi>j(ThusU and R have the same structure; the different mnemonics are purely historical.)There are many variations on the above problem types depending on the matrix properties.
For instance,a matrix may be categorized by:m, and the number of columns, n;•Size, that is, how large are the number of rows,•Presence of complex elements, otherwise the matrix is real;•"Shape", that is, "tall" if•The pattern of non-zero elements, for example, upper- or lower-triangular as presented above,diagonal if Aij = 0 if i≠j , banded if Aij = 0 if j-i > k, where k is a small integer.•The existence of mathematical properties such as positive definiteness or norm of the matrix, orproperties about the values, e.g., a Toeplitz matrix, which has all elements on any diagonal of equalvalue.•The proportion of non-zero elements to the total, where a small proportion of non-zero elements givesa sparse matrix, whereas a high proportion gives a dense one.Band matrixxxx0000000xxxx000000xxxxx000000xxxxx000000xxxxx000000xxxxx000000xxxxx000000xxxxxLower triangular matrix000000xxxx0000000xxxTridiagonal matrixxx00000000xxx00000000xxx00000000xxx00000000xxx00000000xxx00000000xxx00000000xxx0m >> n, "fat" if m << n, square if m = n;0000000xxxxxxxxxxxxx0xxxxxxxxx00xxxxxxxx000xxxxxxx0000xxxxxx00000xxxxx000000xxxx0000000xxx00000000xx000000000xHessenberg matrixxx00000000Upper triangular matrix00000000xxx000000000xx00000000xxx0000000xxxx000000xxxxx00000xxxxxx0000xxxxxxx000xxxxxxxx00xxxxxxxxx0xxxxxxxxxxxxx0000000xxxx000000xxxxx00000xxxxxx0000xxxxxxx000xxxxxxxx00xxxxxxxxx0xxxxxxxxxxxxxxxxxxxxBordered matrixx00000000x0x0000000x00x000000x000x00000x0000x0000x00000x000x000000x00x0000000x0x00000000xxxxxxxxxxxx18Copyright © 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 JournalDue to the great variety of types of matrices, there are many hundreds of problems and methods to solvethem, but few users will want to explore such specialization unless a particular class of linear algebraproblem is solved frequently. Few users have the resources and energy to acquire and maintain a largecollection of software, so will generally prefer a few more general tools of wide applicability.Matrix Calculations Without (Explicit) MatricesIn our experience only a few real problems have necessarily involved matrices much larger than 20columns or rows. We say "necessarily larger" because many large problems are the result of injudiciousproblem formulation (Chapter 13).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
