1 *********************************************************************** + THE LIBRARY NUMAL OF ALGOL 60 PROCEDURES IN NUMERICAL MATHEMATICS PROGRAM TEXTS AND DOCUMENTATION *********************************************************************** VOLUME 0 GENERAL INFORMATION AND INDICES VOLUME 1 ELEMENTARY PROCEDURES VOLUME 2 ALGEBRAIC EVALUATIONS VOLUME 3 LINEAR ALGEBRA VOLUME 4 ANALYTICAL EVALUATIONS VOLUME 5 ANALYTICAL PROBLEMS VOLUME 6 SPECIAL FUNCTIONS AND CONSTANTS VOLUME 7 INTERPOLATION AND APPROXIMATION MATHEMATICAL CENTRE , AMSTERDAM 4-TH REVISION, 1980 1 NO PART OF THE LIBRARY NUMAL MAY BE REPRODUCED, STORED IN A RETRIEVAL SYSTEM, OR TRANSMITTED, IN ANY FORM OR BY ANY MEANS, ELECTRONIC, PHOTOCOPYING, RECORDING, OR OTHERWISE, WITHOUT THE PRIOR WRITTEN PERMISSION OF THE ACADEMIC COMPUTING CENTRE AMSTERDAM (SARA) OR THE MATHEMATICAL CENTRE (AMSTERDAM). 1 THE LIBRARY NUMAL OF ALGOL 60 PROCEDURES IN NUMERICAL MATHEMATICS CONTENTS OF VOLUME 0 GENERAL INFORMATION AND INDICES 0 .1 GENERAL INFORMATION 0 .2 SYSTEMATICAL INDEX 0 .3 INDEX BY CODE NUMBER 0 .4 KWIC INDEX 1GENERAL INFORMATION (JANUARY 1980) PAGE 1 INTRODUCTION. AT REQUEST OF THE ACADEMIC COMPUTING CENTRE OF AMSTERDAM (SARA) THE MATHEMATICAL CENTRE STARTED IN 1973 THE ADAPTATION OF ITS COLLECTION OF NUMERICAL PROCEDURES FOR USE WITH THE CD CYBER 70 SYSTEM. THE RESULTING NUMERICAL LIBRARY IS CALLED "NUMAL" ( "NUM" ERICAL PROCEDURES IN "AL" GOL 60 ). THE DOCUMENTATION APPEARED IN 1974 IN A LOOSE LEAF MANUAL. IT WAS REVISED AND UPDATED IN 1975, 1977 AND 1979. IN THIS PERIOD THE LIBRARY GREW TO A COLLECTION OF ABOUT 430 ROUTINES IN ALL DIFFERENT FIELDS OF NUMERICAL MATHEMATICS. ALTHOUGH NO ATTEMPTS HAVE BEEN MADE TO CREATE A COLLECTION THAT GIVES A COMPLETE OVERVIEW OF ALL NUMERICAL PROCEDURES AVAILABLE, MOST AREAS OF NUMERICAL MATHEMATICS ARE COVERED AND MOST PROGRAMS FOR WHICH A NEED WAS FELT HAVE BEEN IMPLEMENTED. THE AIM OF NUMAL WAS TO PROVIDE ALGOL 60 PROGRAMMERS WITH A HIGH LEVEL NUMERICAL LIBRARY WHICH CONTAINS A SET OF VALIDATED NUMERICAL PROCEDURES TOGETHER WITH SUPPORTING DOCUMENTATION. THE LIBRARY HAS BEEN CONSTRUCTED IN A MODULAR WAY: MOST ROUTINES REFER TO AND RELY ON OTHER ROUTINES THAT PERFORM A WELL-DEFINED SUB-TASK. THE MORE EXPERIENCED USER CAN AVAIL HIMSELF OF THESE MORE ELEMENTARY ROUTINES IN THE SAME WAY AS THE AUTHORS OF THE LIBRARY DO. THE NOVICE, IT IS BETTER TO USE THE MORE COMPREHENSIVE PROCEDURES WHICH PERFORM COMPLETE MATHEMATICAL COMPUTATIONS. IN 1976 AND 1977 THE NUMERICAL MATHEMATICS DEPARTMENT ORGANIZED A SEMINAR ON NUMERICAL SOFTWARE. IN THIS SEMINAR THE USE OF SOME ALGOL PROCEDURES IN THE NUMAL LIBRARY WAS EXPLAINED IN DETAIL AND THEIR ALGORITHMIC BACKGROUND WAS CLARIFIED. ALSO, THE NUMERICAL LIBRARIES IMSL (FORTRAN), NAG (ALGOL 60 AND FORTRAN) AND NUMAL (ALGOL 60) WERE COMPARED. THE PROCEEDINGS OF THIS SEMINAR APPEARED (IN DUTCH) IN THE MC-SYLLABUS SERIES OF THE MATHEMATICAL CENTRE AS: COLLOQUIUM NUMERIEKE PROGRAMMATUUR, DEEL 1 J.C.P.BUS ED., MCS 29.1, MATHEMATISCH CENTRUM, AMSTERDAM,1976, AND COLLOQUIUM NUMERIEKE PROGRAMMATUUR, DEEL 2 H.J.J.TE RIELE ED., MCS 29.2, MATHEMATISCH CENTRUM, AMSTERDAM,1977. 1GENERAL INFORMATION (JANUARY 1980) PAGE 2 THE LANGUAGE ALGOL 60 AND THE MODULAR STRUCTURE TWO IMPORTANT CHARACTERISTICS OF NUMAL ARE : ITS MODULAR STRUCTURE AND THE CONSISTENT USE OF STANDARD ALGOL 60 (IN THE SENSE OF THE REVISED REPORT ON ALGOL 60, REF.) INPUT AND OUTPUT ROUTINES, NOT BEING DEFINED IN STANDARD ALGOL 60, HAVE NOT BEEN USED IN THE LIBRARY SOURCE TEXTS. THEY ONLY APPEAR IN THE DOCUMENTATION WHERE EXAMPLES OF USE OF THE LIBRARY ROUTINES ARE GIVEN. SINCE DOUBLE PRECISION IS ALSO NOT DEFINED IN ALGOL 60, A SMALL NUMBER OF DOUBLE PRECISION ARITHMETIC ROUTINES COULD NOT BE CODED IN ALGOL 60 AND ,HENCE, A FEW (8) DOUBLE PRECISION MODULES WERE CODED IN ASSEMBLY LANGUAGE. EXCEPT FOR THIS SMALL NUMBER OF DOUBLE PRECISION ARITHMETIC ROUTINES ALL THE SOURCE TEXTS ARE WRITTEN IN ALGOL 60 AND ,HENCE, THEY ARE IN PRINCIPLE INDEPENDENT OF THE COMPUTER/COMPILER USED (REF.). IN ITS PRACTICAL IMPLEMENTATION ON THE CDC-CYBER SYSTEM MOST ELEMENTARY ROUTINES IN THE MODULAR STRUCTURE OF THE LIBRARY ( I.E. THE MATRIX AND VECTOR OPERATIONS ) WERE RE-CODED BY HAND IN ASSEMBLY LANGUAGE. THIS HAS ACCELERATED THE OPERATION OF MOST LINEAR ALGEBRA ROUTINES BY A FACTOR 2.5. THUS, ONE OF THE MAJOR DISADVANTAGES OF THE USE OF ALGOL 60, THE RELATIVELY LONG EXECUTION TIMES ( WHICH FIRST WERE APPROXIMATELY 4 TIMES LONGER THAN FOR AN EQUIVALENT FORTRAN PROGRAM ) WAS CIRCUMVENTED TO A LARGE EXTENT. THIS REFINEMENT WAS POSSIBLE BECAUSE OF THE CONSISTENT APPLICATION OF THE MODULARITY PRINCIPLE. REFS. P.NAUR (ED.) REVISED REPORT ON THE ALGORITHMIC LANGUAGE ALGOL 60 A/S REGNECENTRALEN, COPENHAGEN, 1964. P.W.HEMKER CRITERIA FOR TRANSPORTABLE ALGOL LIBRARIES. IN: PORTABILITY OF NUMERICAL SOFTWARE (W.COWELL ED.) LECTURE NOTES IN COMP.SC. 57,SPRINGER VERLAG, 1977. 1GENERAL INFORMATION (JANUARY 1980) PAGE 3 ORGANIZATION OF THE LIBRARY. EACH ROUTINE IN THE LIBRARY IS IDENTIFIED BY A NAME AND A CODE NUMBER. THE CODE NUMBER CAN BE USED IN AN ALGOL 60 PROGRAM WHEN REFERENCE IS MADE TO A PRE-COMPILED PROCEDURE IN THE OBJECT CODE LIBRARY. ALL PROCEDURES IN NUMAL ARE CLASSIFIED ACCORDING TO SUBJECT. THE SUBJECTS ARE IDENTIFIED BY A SECTION NUMBER. THE MANUAL IS ORDERED BY THESE SECTION NUMBERS. IN ORDER TO FIND A PARTICULAR PROCEDURE, THERE IS A SYSTEMATIC INDEX IN WHICH ALL PROCEDURES ( THEIR NAMES AND THEIR CODE NUMBERS ) ARE RECORDED AND CLASSIFIED BY THEIR SECTION NUMBER ( I.E. BY SUBJECT ). FOR CROSS REFERENCING THERE IS AN INDEX BY CODE NUMBER, WHICH HAS REFERENCES TO PROCEDURE NAME AND SECTION NUMBER, AND THERE IS ALSO A KWIC INDEX IN WHICH KEYWORDS AND PROCEDURE NAMES HAVE BEEN ORDERED ALPHABETICALLY. THE STATUS OF NUMAL IN 1979 THE INTEREST AT THE MATHEMATICAL CENTRE IN THE CREATION OF GENERAL NUMERICAL SOFTWARE IN ALGOL 60 DECREASED AND THE DRAFTING-COMMITTEE DECIDED TO CONCLUDE THE NUMAL-PROJECT WITH THE PUBLICATION OF A FINAL REVISION OF THE LIBRARY IN BOOK FORM. IN ITS PRESENT FORM THE LIBRARY NUMAL CAN BE SEEN AS A DESCRIPTION OF THE STATE-OF-THE-ART OF NUMERICAL ALGOL 60 PROGRAMMING AT THE MATHEMATICAL CENTRE AT THE END OF THE 1970-S. WE THINK THAT IT CONTAINS A VALUABLE COLLECTION OF ROUTINES IN A LANGUAGE THAT STILL CAN DESCRIBE NUMERICAL PROCEDURES BETTER THAN MANY OTHER PROGRAMMING LANGUAGES CURRENTLY IN USE. 1GENERAL INFORMATION (JANUARY 1980) PAGE 4 IMPERFECTIONS AND RESPONSIBILITY. ALTHOUGH THE NUMERICAL MATHEMATICS DEPARTMENT OF THE MATHEMATICAL CENTRE ASSUMES THE RESPONSIBILITY FOR IMPERFECTIONS BOTH IN PROGRAMS AND IN DOCUMENTATION, NEITHER THE MATHEMATICAL CENTRE NOR THE AUTHORS/CONTRIBUTORS ACCEPT RESPONSIBILITY FOR THE CONSEQUENCES OF SUCH IMPERFECTIONS. ALTHOUGH MUCH EFFORT HAS BEEN SPENT TO KEEP THE NUMBER OF ERRORS TO A MINIMUM, IT IS POSSIBLE THAT SOME MINOR ERRORS STILL REMAIN. THEREFORE THE NUMERICAL MATHEMATICS DEPARTMENT WILL KEEP A LIST OF ALL ERRORS IN THE DOCUMENTATION AND/OR THE PROGRAMS THAT BECOME KNOWN AFTER PUBLICATION AND THIS LIST WILL BE MADE AVAILABLE UPON REQUEST. NUMAL IN FORTRAN. A TRANSLATION OF NUMAL INTO A FORTRAN VERSION SUITABLE FOR USE ON A MINI-COMPUTOR IS CARRIED OUT UNDER THE SUPERVISION OF P.WYNN BY H.T.LAU IN THE SCHOOL OF COMPUTER SCIENCE, MC-GILL UNIVERSITY, MONTREAL, CANADA. FURTHER RESEARCH ON THE FORTRAN VERSION IS ALSO BEING CARRIED OUT AT IIMAS (INSTITUTO DE INVESTIGACIONES EN MATEMATICAS APPLICADAS Y EN SYSTEMAS), UNIVERSIDAD NACIONAL AUTONOMA DE MEXICO. ORIGIN OF THE PROGRAMS. THE MAJOR PART OF THE LIBRARY CONSISTS OF PROCEDURES THAT HAVE BEEN DEVELOPED AT THE MATHEMATICAL CENTRE. HOWEVER, SOME PROCEDURES ARE ADAPTED VERSIONS OF PROCEDURES PUBLISHED IN THE OPEN LITERATURE. IN PARTICULAR A NUMBER OF PROGRAMS ARE DERIVED FROM PROCEDURES PUBLISHED BY A. BJOERCK, R. BULIRSCH, J.R. BUNCH, G.H. GOLUB, L. KAUFMAN, B. LINDBERG, B.N. PARLETT, C. REINSCH AND J. STOER. 1GENERAL INFORMATION (JANUARY 1980) PAGE 5 LIST OF CONTRIBUTORS AND AUTHORS OF PROCEDURES IN NUMAL. J.J.G. ADMIRAAL M. BAKKER J.KOOPMAN P.A. BEENTJES G.J. LAAN J.C.P. BUS C.G. VAN DER LAAN C.H. CONVENT R. MONTIJN T.M.T. COOLEN R. PLOEGER J. DANIEL T.H.P. REYMER K. DEKKER H.J.J. TE RIELE TH.J. DEKKER C.J. ROOTHART B. VAN DOMSELAAR H.G.J. ROZENHART H. FIOLET E. SLAGT H.N. GLORIE N.M. TEMME P.J. HARINGHUIZEN J.G. VERWER P.W. HEMKER M. VOORINTHOLT W. HOFFMANN D.T. WINTER P.J. VAN DER HOUWEN J. WOLLESWINKEL S.P.N. VAN KAMPEN A.C. YSSELSTEIN J. KOK J.A. ZONNEVELD ACKNOWLEDGEMENTS. THE LIBRARY NUMAL HAS BEEN DEVELOPED BY THE JOINT EFFORTS OF THE MEMBERS OF THE LIBRARY GROUP OF THE NUMERICAL MATHEMATICS DEPARTMENT OF THE MATHEMATICAL CENTRE. IN PARTICULAR, HOWEVER, WE WANT TO ACKNOWLEDGE THE MEMBERS F. GROEN, K. VAN 'T HOFF, R. PISCAER, B.P. SOMMEIJER, G.J.F. VINKESTEYN, WHO TOOK CARE OF FILE MANIPULATION, EDITING OF THE DOCUMENTATION FILES AND ADAPTION AND RUNNING OF THE KWIC INDEX PROGRAM. FURTHER WE WANT TO ACKNOWLEDGE THE MEMBERS OF THE DRAFTING COMITTEE: C.DEN HEYER, P.J.VAN DER HOUWEN, J.KOK, N.M.TEMME AND D.T.WINTER, AND THE EXTERNAL ADVISORS: TH.J.DEKKER, W.HOFFMANN (UNIVERSITY OF AMSTERDAM) AND C.G. VAN DER LAAN (UNIVERSITY OF GRONINGEN). P.W. HEMKER GENERAL EDITOR 1SYSTEMATICAL INDEX (JANUARY 1980) PAGE 1 CLASSIFIED ACCORDING TO SUBJECT, THIS INDEX CONTAINS THE NAMES OF THE PROCEDURES AND THE CORRESPONDING CODE NUMBERS. THE DOCUMENTATION OF THE PROCEDURES IS PRESENTED IN VOLUMES 1 THROUGH 7 AND IS ARRANGED ACCORDING TO SECTION NUMBERS. HENCE REFERENCE IS IMMEDIATE. IN ADDITION TO THE CODE NUMBER AND THE NAME OF EACH PROCEDURE THE MONTH OF FIRST APPEARANCE OF THE FINAL DOCUMENTATION IS LISTED. DIRECTIONS TO OBTAIN A PIECE OF DOCUMENTATION IN MACHINE READABLE FORM (ONLY FOR USE WITH THE CDC CYBER 70 SYSTEM). IN ORDER TO OBTAIN A PIECE OF DOCUMENTATION IN MACHINE READABLE FORM ONE SHOULD AVAIL OF THE NUMAL DOCUMENTATION FILE. THIS FILE MIGHT BE AVAILABLE AT YOUR COMPUTER CENTER EITHER ON A MAGNETIC TAPE OR AS A PERMANENT FILE. THE DOCUMENTATION FILE CONSISTS OF AN EVEN NUMBER OF RECORDS (LEVEL 0) EACH SECTION OF THE NUMAL DOCUMENTATION CAN BE FOUND IN TWO SUCCESIVE RECORDS ON THIS FILE. THE FIRST RECORD CONSISTS OF THE DESCRIPTION OF THE PROCEDURE(S) IN THAT SECTION, THE SECOND RECORD CONTAINS THE SOURCE TEXT(S). FOR EACH SECTION OF THE NUMAL DOCUMENTATION THE RECORD NUMBER OF THE FIRST OF THE TWO RECORDS CAN BE FOUND IN THE LAST COLUMN OF THE SYSTEMATICAL INDEX. EXAMPLE : AT THE SARA COMPUTER CENTER (AMSTERDAM), THE DOCUMENTATION FILE IS AVAILABLE AS THE SECOND FILE ON TAPE VSN=S8328I. TO OBTAIN THE DESCRIPTION AND THE SOURCE TEXT OF THE PROCEDURE "MULTISTEP" ( SECTION 5.2.1.1.1.1 , RECORD NUMBER 151 ) FROM THE DOCUMENTATION FILE, THE FOLLOWING CONTROL CARDS CAN BE USED LABEL,TAPE,R,L=NUMAL,ID=MC,D=PE,VSN=S8328I. SKIPF,TAPE,1,17. SKIP THE FIRST FILE ON TAPE SKIPF,TAPE,150. SKIP 150 RECORDS COPYBR,TAPE,OUTPUT,2. COPY TWO RECORDS FOR USE WITH THE CD CYBER SYSTEM, THE OBJECT CODE OF THE PROCEDURES IS AVAILABLE AND IS CONTAINED IN THE LIBRARY FILE "NUMAL3". THIS LIBRARY FILE CAN BE USED WHEN PROGRAMS COMPILED UNDER ALGOL3 ARE LOADED. FOR USE OF A LIBRARY FILE SEE E.G. CDC SCOPE REF. MANUAL, CHAPTER 6, OR THE CDC INTERCOM REF. MANUAL, CHAPTER 3, XEQ COMMAND.