FORM Matters: Fast Symbolic Computation under - LaCIM
Contents
1. define N 100 ocal T1 1 ocal T2 1 iocal T3 2 do i 4 N Sort drop T i 3 Skip T i 2 Skip T i 1 Local Ti e T i lje T i 2 Tt gphe3 s print nddo T4 4 T5 7 T99 53324762928098149064722658 end T100 98079530178586034536500564 All programming commands are echoed to output when executed On our test hardware an AMD Athlon XP 1800 MHz 1 GB RAM the execution of the entire program takes on the average about 3 milliseconds You can check your system s timing by commenting out nwrite statistics at the start of the program Then in ad dition to the total timing FORM will also inform you about the intermediate execution timings and will pro vide statistics on the terms generated with their memory usage If you have a conventional computer algebra system at home try to run the same recursive algorithm and observe how long it takes to obtain this result Amazingly on the same hardware setup Mathematica 5 0 requires already 28 minutes to calculate Tss T This is largely due to the memory management of the interme diate results 74 734 during the computation Mathe matica and similar algebra systems will store all results in memory whereas FORM allows to handle memory con sumption in the intermediate steps more efficiently Let s study the Tribonacci code in more detail and see how FORM achieves such impressive results Fir2. stead of the full range up to 2x P We still can recover complete knowledge of the sine with this double angle formula sin 2x 2 sin x cos x Making it more difficult for us we now suppose knowing only one third one fourth one n th of the 27 range Nevertheless we can always expand our knowledge to full scope Salvation comes from the following recursive rela tion sin nx 2sin n 1 x cos x sin n 2 x Example 2 implements this algorithm in FORM and computes sin 10x Simpl fication cof Multi Angle Sines De ge sama cosy Symbols x k7 BUNCE Ons sin eo s Local expr sin 10 x repeat Id SINO a OF ra SIn Sumi Gea id sin k x 2 RS in EEI ACOS X 15 onk se ice endrepeat id sin x id cos x cos x 20 printe end Execution took just 10 milliseconds on our test machine with the final output 0 01 sec expr Generated terms Terms in output Bytes used Time expr 512 Sin x cos x 1024 sin x cos 672 sin x cos x 160 sin x cos x 10 sin x cos x m OX FORM has successfully reduced our symbolic input on line 9 to a sum of powers of simple sines and cosines there is no more dependence on multiple angles in the ar guments A look at the program code shows that before work ing with the local variable expr we have to define the involved symbols and functions see lines 6 7 Sy
3. Mathematics with Applications 2004 3 NIKHEF Ftp Repository at tp ftp nikhef 7 G J van Oldenborgh An Introduction to FORM 26p Older FORM vl x binaries for most common UNIX flavors and of course Linux can be downloaded from this ftp site The original FORM manual and other shorter introductions are also located at this site J A M Vermaseren FORM 252p Amsterdam 1989 This is the original reference to FORM v1 x J A M Vermaseren Symbolic Manipulation with FORM Tutorial and Reference Manual 113p Am sterdam 2002 The new handbook that deals with FORM 3 It is a revised and enlarged version of the previous reference manual for FORM 2 A Heck FORM for Pedestrians CAN Exper tise Center and University of Petr polis Petr polis 1993 ibid with J A M Vermaseren 149p Ams terdam 2000 An introduction with many good ex amples and exercises It was updated and extended to FORM 3 10 M M Tung Leiden 1995 A concise introduction with some ad vanced math and physics applications 8 S Plouffe Plouffe s Tables of Constants University of Quebec Montreal 1999 A short note on how to calculate Tribonacci numbers without recursive al gorithms is located at 9 The Vim Homepage located at Binaries and source code are available for download Vim coloring scheme for syn tax elements in FORM Mainz 2001 located allhttp uu vim org htmldoc syntax hhtm1 f
4. just use these values By issuing the skip command on lines 16 and 17 FORM will keep these variables inac tive within the current module This means that within this range all subsequent commands will have no effect on these variables In fact here we suppress the multiple output of already calculated T s Hence the print command of line 21 only acts on the local variable 7 4 which is calculated from its lower three neighbors according to the given recursive relation for each loop l 1 2 In the last step after all cycles of the do loop are completed the end directive gracefully exits the pro gram l After several hours we lost patience computing 7199 Mathematica s own extrapolation tool suggests that this calculation will require more than 3 months M M Tung Computers amp Mathematics with Applications 2004 Pattern matching Multi angle trigonometry Naturally FORM unleashes its full power when sym bolic expressions are involved Thus in this example we will deal with fast symbolic recursion and simple pattern matching Since ancient times mathematical functions have been investigated and charted in huge tables Usually the function values for a set of arguments is given and then supplemented by appropriate rules These rules are de signed to extrapolate the results out of documented range Let s assume we would only know the infamous sine and cosine functions for values ranging from 0 to x in
5. PCs with lower memory it was recommended to set the num ber of symbols one would work with at a time and also set the number of statements in one unit of execu tion This simple setup should work on most machines On older PCs perhaps you will have to tweak some of the parameters that control buffer and heap sizes most notably WorkSpace LargeSize SmallSize and MaxTermSize In chapter 9 of the user manual you find all 36 parameters cataloged and explained If you should have to change any of these parameters to tailor your machine s hardware consult these guidelines first If you have worked out a parameter config uration that you want to make the system wide default copy form set to a standard directory as etc or usr local share or perhaps to local share for an installation on a particular ac count without root privileges We have written the following wrapper program in the Bourne Again SHell to assist you when running FORM The program reads the system wide parameter defaults with possible override from local form set files and provides additional useful features that the FORM binary does not directly implement M M Tung Computers amp Mathematics with Applications 2004 bin bash form simple wrapper for FORM FORMBIN form3 1 FORMSET etc form set not necessary to modify anything below this line abs 9 f UES aS I ee iota aah echo form You must specify a
6. of the second example pro gram within the graphical mode of vim enter gvim example2 frm on the command line For automatic syntax highlighting put syntax on into the vim config uration file vimrc Adding the flag let form enhanced color 1 into vimrc produces a slightly modified coloring that distinguishes better between various FORM command types All recent distributions of vim the current stable re lease is v6 3 already include FORM syntax highlighting However it can also be easily installed on any recent vim installation without doing a full upgrade In this case download the syntax file form vim from the vim homepage 9 and follow the instructions in vim s help entry help mysyntaxfile Usually vim detects FORM files by the extension frm Appending to the FORM code the modeline vim ft frm forces vim to use the rm filetype whatever extension the input file has The FORM parser will not know about the modeline as it appears after the end statement While working on a program it would be quite cum bersome to exit the editor window every time significant modifications are made and you want to run FORM The following definition in the vimrc shortcuts this tedious edit and run cycle and is very helpful for fast prototyping of programs map E uw s oRCEormss dl SOR S split basename frm log lt CR gt O e lt CR gt lt CR gt This mapping binds the key sequence
7. starting values are Tj 1 T 1 and T3 2 Following this rule we obtain 74 by taking the sum of the three previous numbers in sequence namely T4 14 1 2 4 To build all higher numbers we have to proceed in a similar fashion The FORM program to compute e g the first 100 Tribonacci numbers will work in the same way Here is the program that implements this algorithm M M Tung Computers amp Mathematics with Applications 2004 Tribonacci Numbers nwrite statistics 5 define N 100 OGA TB SET ical T2 1 10 ioca 32s dori Ae aN ZSCORE IKOPRI O 15 SKRIO SKIPA Toc au IR E A her NE ah ae ALG ake Syn 20 print enddo end Note that as for the configuration file the comment char acter is Wherever a line begins with an asterisk the remainder of the line is ignored This does not conflict with the multiplication sign as there is always a factor in front of the multiplication Here we have given the program a short description at the beginning of the file Of course comments can be included in all parts of the coding The next observation is that all lines are terminated with a semicolon except for those with commands that start with the prefixes and FORM distinguishes between three classes of commands which becomes evi dent from these punctuation rules When running a pro gram the behavior of commands of each class i
8. would have produced the more lengthy input frm log One greater advantage of the wrapper over the naked FORM binary is that it accepts multiple file input For example the command line Form BEML Erm temp f 2 0st TS A SS EEM creates log files distributed correctly over the file system always grouping source and output nicely together Also for multiple file input local parameter settings will be used instead of system wide defaults This check is done individually for every input file on the command line Programming FORM sets itself apart through its intentionally restricted set of basic instructions and its terse syntax Once ac customed to the general syntax principles you can quite easily extend your working knowledge by looking up advanced or more specialized commands in the FORM Manual and in various tutorials 5 6 7 This section is intended to get you started fast and introduce you to the main features of FORM s programming language For this purpose we will treat various mathematical problems and take a closer look on how FORM solves them As we go on each problem will present you new aspects and techniques of FORM programming Getting started Tribonacci numbers Let s start with a slightly modified classic from computer Science that involves recursive programming Tribonacci numbers are generalized Fibonacci numbers which obey the following recursive relation T Th 1 Tn Th 3 where the three
9. FORM Matters Fast Symbolic Computation under UNIX Michael M Tung Instituto de Matematica Multidisciplinar Universidad Polit cnica de Valencia P O Box 22 012 Valencia Spain Abstract We give a brief introduction to FORM a symbolic programming language for massive batch operations designed by J A M Vermaseren In particular we stress various methods to efficiently use FORM under the UNIX operating system Several scripts and examples are given and suggestions on how to use the vim editor as development platform Keywords Computer algebra FORM programming UNIX In the past few years we have experienced rapid progress in the field of computer algebra on desktop PCs Only two decades ago many algebraic compu tations would have been thought impossible to perform on machines other than supercomputer powerhorses To day every college student is accustomed to solving his math or physics homework assignments with comfort able computer algebra environments such as Mathemat ica Maple V Macsyma and Reduce just to name the most prominent of such programs These modern computer algebra systems incorporate a vast amount of mathematical knowledge ranging from extensive integral tables to obscure properties of special functions and fancy graphical output However there are some drawbacks Although almost all of these mathemat ical geniuses contain high precision routines to give nu merical output very few people would seri
10. fy commands replace the sine and cosine functions by their corresponding symbols NB Note that there still exist many exotic but in particular cases extremely useful functions that are not yet implemented on computer hardware In practice this simple example for the unproblematic sine function can be generalized and applied to these functions 407 102 REFERENCES AND RESOURCES M M Tung Computers amp Mathematics with Applications 2004 FORM automatically contracts the powers of symbols but by default not for functions Hence without this trick the final expression would still contain many uncontracted identical factors The program concludes with the usual print state ment and end directive FORM Development with Graphical Support FORM programs are run in batch mode One creates files containing instructions with an editor let FORM process the file and investigates the output During the devel opment of such a program this edit and run cycle is re peated as many times as necessary Especially for large programs which often have to run unattendedly this strat egy has proven very efficient Our favorite editing tool is the vim editor 9 an im proved version of the ubiquitous vi which adds many powerful features to the original Apart from its standard editing capabilities vim can support FORM development by e using syntax color highlighting e executing programs interactively shows a screenshot
11. is statically linked for GNU Linux 2 2 5 and will normally run on older Linux systems Release versions prior to version 3 are to be found at NIKHEF s ftp site B 4 However these bi naries are dynamically linked to the older libc so library and will only execute on newer glibc2 systems with back wards compatibility After the download place the binary somewhere into your path perhaps usr local bin and don t forget to set it chmod 755 In the following we will assume that you have named the binary form3 1 Test at this stage that you get the following output when entering form3 1 Correct use is v oim gt inputfile options FORM runs exclusively in batch mode working through a list of commands given in the input file Unfortunately there is no h option to present you with more informa tion The FORM Manual which is also available in PDF format at NIKHEF s site gives further details 5 Fortunately there are only a few important options that are relevant for setting up things correctly The op tion s filename specifies where FORM should look for parameter settings The default filename is form set If this file is placed in the current direc tory where the FORM code to be run is located it will override all other settings Thus only if there is no lo cal form set it makes sense to use the s option If no form set file is present at all FORM will assume built in defaults which in mos
12. m bols names are composed out of alphanumeric characters where the first character always has to be a letter Be care ful FORM is case sensitive with respect to symbol and function names Anything between square brackets is not interpreted by FORM Here sin x and cos x are symbols as x and k Functions are symbols that take arguments Lines 11 to 17 are the central part of the program The repeat and endrepeat statements embrace com mand blocks that are to be executed as long as the local variable doesn t change anymore Our expression is the function sin 10 x It has two arguments the first gives the numeric factor n and the second the free vari able x The FORM statement identify a b acts on the current local variable s and replaces all terms a by b Hence lines 12 and 13 trivially reduce sin 0 x 0 and sin 1 x sin x No further decomposition beyond this point is possible Lines 14 to 16 demonstrates how pattern matching can be used with the identify statement The first ar gument k is a placeholder which translates as k to the right hand side of this substitution rule So in the initial pass of the repeat loop sin 10 x is reduced to combi nations of sin 9 x and sin 8 x In the next run also to sin 7 x and sin 6 x and so on The decomposition fi nally comes to an end with an expression expr that only contains immutable terms sin x paired with various fac tors and cos x Thelasttwo identi
13. mpact Both commands always come in pairs and embrace a code fragment that is to be run several times In this case lines 14 to 19 are expanded N 3 times starting with i 4 and incrementing up toi N After this expansion FORM actually executes the code Without the do loop we would have required 6 x N 3 lines not counting additional blank lines with the same final result In FORM all commands are case insensitive So in lines 9 11 we could have written local instead of Local Writing commands with initial major letters serves to highlight certain program passages for the hu man reader FORM will interpret the program in the same manner irrespective of the case used for the commands On the other hand variable names and strings are case sensitive for the sole purpose to offer the program mer more flexibility Thus changing the argument of the define macro in the Tribonacci example from N to n will inevitable result in an execution error Use your favorite editor to enter the code of examplel frm Then run the program by entering form examplel frmon the command line The out put will be written to standard output and logged to the file examplel log This is what the log file should contain FORM by J Vermaseren version 3 1 Jan 24 2003 Run at Thu Jun 10 18 36 44 2004 Tribonacci Numbers nwrite statistics M M Tung Computers amp Mathematics with Applications 2004
14. n input file echo form lt filel gt lt file2 gt exit iEn for i in S do ETLE echo oi I sed sA frms BASE basename 1 DIR echo i sed s SBASI CJ Gop echo wn et I f SDIR formeset then SFORMBIN s DIR form set i gt tee SFILE log else SFORMBIN s FORMSET i gt tee SFILE log agat echo e Xn FORM output to gt SFILE log n Make sure that the two environment variables FORMBIN and FORMSET point to the FORM binary and parameter file on your system respectively If the binary is placed somewhere in the main path it won t be necessary to in clude the full path for FORMBIN But you always have to specify the full path for FORMSET FORM cannot find a local form set file when call ing an input file from an external directory and will use the built in defaults instead But calling the wrapper pro gram with form work new inputfile will automatically read a corresponding parameter file form set in the directory work new if present The wrapper will also produce a log file in the same directory as the input code without making use of the l command line option of FORM This way name handling of the log files is much more flexible If you enter form input frm using frm as the stan dard extension for FORM your log output will be input log This ensures compatibility with the 1 op tion of FORM 1 which
15. orm vim and ftp fep home vim M M Tung Computers amp Mathematics with Applications 2004 REFERENCES AND RESOURCES deH H dug xaje L1 d 4 eA x l DPL YFF GwwWltust TAv2O WHOS 3 dOd opulw ula D ud04 234 AJUTS X TJ TS x gjuts UTS y sayng xeju c 7p 40 UOT eX MITES pus 1 qurad X SO2 pT X UTS PT fyzeodsupus fig 11u9pT fig 11u9pT fig1T1u9pT qe d a Adxa 620 uot zOUNn 4 x sToquis TFT TAWts ii ae gmme sjooL wal p3 ald angle sine example with vim syntax highlighting Figure 1 Multi M M Tung Computers amp Mathematics with Applications 2004 REFERENCES AND RESOURCES GT TE O00 8 IB disi 304 diyjug xeiei xal 1Wv20 WHOd P ZUEUED Ta LH Lu t Z2 C uexat ISxz x j urs fiyr1uepr X uIS fIjurs figrauepr 0 xf OJuTtTS fiyT1uepr qe d a X udxa peoo1 UTS uor3oun Jf gt x sToqufis xX arcu 40 UOTIEITYTTAWTS x X OT UTS udxa Tes07 E m a SEN s S uUT I5ug ra3rIni jo uorjearj4r durs unp any 3e uns f00Z PZ uep rl ge uorsaae uasJ4aseuasA p fig wsodll ae GaG ombiLiY9yqguwug ullAD J dOd mopu sayng xeju s sjoo xe p3 ally Figure 2 Running and logging of the multi sign example with vim 10
16. ously employ them for full scale number crunching in a larger project For maximum performance they will rather choose FOR TRAN or C C for efficient coding and link only es sential libraries to their programs at runtime This avoids unwanted overhead and results in executable code which is small and fast Similar conditions hold also for a certain class of alge bra problems some algebraic computations rather rely on processing large amounts of symbolic data than making use of encyclopedic mathematical knowledge For this kind of formula crunching we require an environment with as little overhead as possible Here one has to sac rifice mathematical versatility and sophisticated graphical user interfaces for brute speed and efficiency email mtung mat upv es If you have to tackle such problems consider to use FORM an algebraic programming language that was specifically designed to manipulate large formulae Jos A M Vermaseren at NIKHEF the Dutch Institute for Nu clear and High Energy Physics created FORM by the end of the 80 s to perform large algebraic calculations in his own research based on a previous project by the Dutch physicist and Nobel prize laureate Martinus J G Veltman Initially only the FORM binaries of the first release 1 0 were available to the public for free For some time later versions 2 x of FORM introduced in 1991 were commercial and sold by Computer Algebra Netherlands Now fortunately and
17. s funda mentally different e Statements and functions require a terminat ing semicolon In our example these are nwrite statistics local drop skip and print A collection of such statements and functions make up one logical unit in a FORM pro gram In FORM jargon such a logical unit is called a module e Directives all start with a period Hence in the Tri bonacci example we call sort and end direc tives Contrary to statements and functions direc tives do not build up the contents of a module but control modules themselves All directives denote the end of a module with certain effects For ex ample the sort directive terminates the previous module and causes all statements within this unit to be executed A FORM program is composed of a sequence of modules where the last module is al ways closed with the end directive e Preprocessor commands begin with and are ex actly what we expect from other programming lan guages They are commands to allow for code frag ments which are expanded before the actual com pilation or execution of a program In our exam ple the define command declares that N is to be replaced by 100 at any further occurrence in the remaining program Note that the argument of define is a string we have to assign 100 to N and later call the macro with N Further important preprocessor commands are do and enddo These commands help to write your code more co
18. st we see that the variable N is set equal to 100 line 7 to make later changes more transparent We could also have supplemented the define command with an ap propriate comment for later revisions of the code In gen eral it is good programming practice to isolate important variables and document their meaning Next we use in lines 9 10 the local statement to define the three local variables 7 1 T 1 and T3 2 FORM also knows global variables but they will only be relevant if you have larger output and want to copy results to a special file In most cases you will probably want to use local variables The local statement serves to declare expressions for FORM to work with Here the expressions are purely numerical In the latter examples expressions will also be symbolical involving both num bers and algebraic terms Now let s move on to the core part of the program As mentioned above the program block from line 14 to 21 is executed 97 times each time incrementing i by one Initially it is i 4 Then we sort the results not much to sort at this point but it will come in handy later On line 15 we drop the local variable 7 3 Tj With this command 7 is cleared from memory upon the next execution of the sort command By doing so we free memory and in principle 7 would again be available for reuse In the present recursive algorithm no operations are directly performed on the current 7 2 and T 1 We
19. t cases will work on stan dard hardware The second option t pathname defines in which directory FORM should store its temporary files As FORM can produce enormously huge intermediate files it is this way possible to redirect temporary output to a partition or device where sufficient physical memory is available If you have one preferred place to store the temporary file you don t need to specify this on the com mand line every time Instead use the entry TempDir in form set The structure of the configuration file is very simple First comes the keyword of the configuration parameter that is followed by the desired corresponding value which can be a number character or string The creation of form set is thus straightforward Here is the minimum configuration we use form set oloba l HORM contig setting up temporary directory TempDir tmp where to look for external code IncDir usr share form scratch which means that one reserves tmp for temporary stor age and adds the directories usr share form and Scratch to the search path to look for additional input files outside the execution directory Commented lines start with an asterisk character The default comment character could be changed by resetting the configuration keyword CommentChar However this is not advisable unless needed since some editors may depend on this de fault setting In older versions of FORM which assumed
20. to great benefit of the scientific com munity release 3 1 dated January 30 2003 is again available for download under the condition that it may not be used for commercial purposes 1 The latest release 3 1 has many new features and the C code has been substantially rewritten improving speed and efficiency In passing from FORM 1 to FORM 2 pattern match ing and manipulation was improved and since then com pression is used to store intermediate and final results on disk With FORM 3 came many additional enhancements among them most notably dynamical variable administra tion with an upper limit of 6000 variables for 32 bit sys tems recursive preprocessor variables and new charac ter string variables 2 In the following we guide you through a quick instal lation of FORM give you a concise introduction to the ba sics of its programming language common to all releases M M Tung Computers amp Mathematics with Applications 2004 M M Tung Computers amp Mathematics with Applications 2004 of FORM and finally show you how to use the vim editor as a powerful workbench for FORM development Installation Installation of FORM is fairly easy As FORM is written in C it has been compiled on many UNIX variants e g HP SGI Solaris MacOSX and Alpha architecture The latest executables for FORM are available for download at NIKHEF s FORM website 1 The Linux executable is of release 3 1 dated January 2003 It
21. to pass the cur rent file through FORM and display the resulting log file in a split window of the same vim session To create a menu button in the toolbar of gvim add for example the following line to gvimrc menu 50 10 amp FORM run form3 1 f The numbers 50 10 indicate the location in the tool bar and will depend on your local vim installation Take a look at the global settings in menu vim to find suitable values that fit your system For example you could easily add another command with the entry menu 50 20 Figure 2 gives a screenshot of gvim running FORM on example2 frm The upper part of the screen displays the corresponding log output in a split window Outlook This has been a brief introduction to FORM and with em phasis on how to use it effectively under UNIX FORM offers many more features to perform advanced and large algebraic computations Most notably with time and ex perience you can build up your own libraries of proce dures that contain specialized routines which solve regu larly occurring mathematical tasks References and Resources 1 NIKHEF FORM Website The National Institute for Nuclear Physics and High Energy Physics Ams terdam The FORM license and latest release can be found at website http www nikhef nl form license html 2 J A M Vermaseren New features of FORM arXiv math ph 0010025 v2 Amsterdam 2000 REFERENCES AND RESOURCES M M Tung Computers amp
Download Pdf Manuals
Related Search