Most of the descriptions are rather brief. If you like to know some more about certain parts of diffop feel free to ask. Description of procedures in diffop. Tools ------------------------ diffop_groundfield Variables: g_conversion1: subs(g_conversion1,A) converts A to the internal syntax for algebraic numbers. g_conversion2: subs(g_conversion2,A) converts A to the RootOf syntax for algebraic numbers. modulus: if this variable <> 0 then some procedures (the ones needed for lifting a factorization, not the ones for producing a factorization) will work modulo this modulus. Typical variable names in procedures: ext: This variable describes the algebraic extension over the field Q. The RootOfs have been replaced by variables `diffop/rootof`.i (i integer) and evala(Expand( )) is replaced by g_expand(expression,ext). ram: This variable gives the ramification. The Laurent series procedures can not handle things like x^(1/2). If a ramification of an expression A is needed it will sometimes be denoted as: [A,ext,ram,`alg over k((x))`]. This means that x in A does not stand for x but ram (which is equal to a constant times x^n) stands for x. So if ram=3*x^5 then x in A stands for RootOf(3*y^5-x,y). Tools: modm : reduce mod modulus if modulus <> 0. g_solve : solve linear equations, also modular g_quotient : compute a/b mod x^n, also modular g_gcdex : extended Gcd, only char 0. g_rem : remainder, only char 0 g_quo : quotient g_factors : calls factors, not modular g_factor : factor(numer( )), not modular degree_ext : degree of the algebraic extension g_expand : expand, not modular. uses g_evala and g_evala_rem g_normal : normal, not modular g_zero_of : Gives root of irreducible polynomial and adapts global variables needed for g_evala v_ext_m : Gives roots, multiplicities and alg extensions of a factored polynomial ext_to_coeffs : coeffs( .. , RootOf's) truncate : mod y^n, with modm truncate_x : mod x^n, without expand or modm g_ext : This procedure gives a list describing the algebraic extensions over Q of a given expression. Laurent series ------------------------ diffop_laurent Global variables: x:=evaln(x) LL accuracy_laurent description_laurent set_laurents value_laurent LL.i are indeterminates which stand for Laurent series. The value of a Laurent series is given by: value_laurent[LL.i]. This value is determined modulo x^accuracy_laurent[LL.i] description_laurent[LL.i]: consists of: [procedure_name, arguments] such that procedure_name(arguments,accuracy) produces the value of LL.i modulo x^accuracy. Procedures: differentiate : gives the derivative of an expression eval_laurent : converts an expression to a Laurent series. new_laurent : used for introducing new Laurent series. new_laurent2 : used by eval_laurent nmterms_laurent : computes a laurent series mod x^n nt : computes an expression mod x^n nterms_expression : used by eval_laurent nthterm_laurent : gives the coefficient of x^n in a Laurent series subsvalueslaurents : name says it all series_val : used by nterms_expression valuation_laurent : the valuation (minimum n with coefficient x^n <>0) ############################## # Computation in k((x))[xDF] #------------------------------------------------ ############################## diffop_local Procedures: Newtonpolygon : Newton polygon, (optionally) including the slopes and Newton polynomials coefs_operator : Used by lift_newton. It returns a block of coefficients of a differential operator. factor_newton : Produces coprime index 1 factorizations, i.e. if the Newton polynomial is reducible, or if there is more than one slope in the polygon, or a combination of these two. factor_newton2 : used by factor_newton factor_op : Produces different kind of local factorizations factor_riccati : This one handles the case where algebraic extensions or ramifications are needed. faster_riccati_split : A factorization method for coprime index > 1 factorizations that uses solving linear equations. The input is a factorization. The output is the same factorization with a faster lift algorithm. indeterminate : Produces an indeterminate indeterminates_op : An operator with undeterminates as coefficients. make_rightfactor : Produces an irreducible right factor in k((x))[xDF] from a 1st order factor in (alg_closure k((x)))[xDF] [factor,ext,ram,`alg over k((x))`]. op_with_slope : Produces an operator with a specified slope and description ram_laur : Ramification of a Laurent series, e.g. subs(x=3*x^5,laurent) ramification_of : Ramification of an expression. rightdivision : right division. skipped_factors : This procedure collects some information used for global factorization. substitute : Non commutative substitution. Procedures for lifting Laurent series: These procedures are only to be called from the Laurent series procedures nmterms_laurent and nthterm_laurent lift_newton: Used for lifting coprime index 1 factorizations f=left*right. lift_ramification: Used for lifting subs(x=ram,f) where ram=constant*x^n lift_rightdivision: Used by rightdivision lift_rightfactor: Used by make_rightfactor lift_rsplit: Used by faster_riccati_split. This procedure calls lift_rsplit2 to lift a factorization f=left*right. If lift_rsplit2 fails to lift this factorization then lift_rsplit will call the slower procedure lift_rightfactor. lift_rsplit2: Used by lift_rsplit. This procedure lifts factorizations that have coprime index > 1 by solving linear equations. If the estimated coprime index is not correct then the lifting may fail. lift_substitute: Used by substitute. Tools for lift_newton: nm_mult: Gives the coefficients between x^n and x^m of a multiplication. nm_block: Gives a part of the differential operator. Similar to the term truncation T_t(f) in my paper. It gives a part of this truncation, e.g. T_7(f)-T_4(f) can be computed by this procedure. nm_block2: Same as the previous procedure except that its input does not consist of an operator with Laurent series coefficients. rem_lift: a global variable. This stores the coefficients that have been computed in a multiplication that were not yet needed but can still be used in a next lifting. Applications: has_liouvillian_solutions: uses symmetric_power and DFactor ############################################### # Solutions of matrix differential equations #-------------------------------- ############################################### diffop_matsol solve_mateqn : compute formal solutions in internal format matrix_mult : used by solve_mateqn. It does a basis transition. cyclic_vector : Compute a cyclic vector and the corresponding basis transisition apply_A : evalm( A*v+diff(v,x) ) left_solutions : Compute a in K[xDF]/(f K[xDF]) s.t. xDF*a = 0 mod f where K is a differential extension of k((x)) xddx_log : Compute derivative of an expression with logarithms. lift_xddx_log : used by xddx_log factor_newton_LCLM : If a local LCLM factorization can easily be obtained (i.e. with coprime index 1) then give one. adjoint : Compute the adjoint. Note that the local and the global adjoint are not compatible. lift_adjoint : used by adjoint rational_solutions : rational solutions of f in k(x)[DF] left_sol_rational : Same as left_solutions but now K=k(x) solve_matrat : compute rational solutions of a matrix diff. eq. ############################# # debugging tools #------------------------------------------------- ############################# diffop_debug test_result: If this procedure is defined then the results of several procedures are automatically checked. This means the computation times will be longer. The time spent on locating a bug drastically decreases. ##################################### # Pade Hermite approximations #----------------------------------------- ##################################### diffop_pade2 The code in this section is derived from Harm Derksen's pade2 (in the Maple share library). lift_pade2 pade2 smaller_pade2 smallest_pade2 valuation_pade2 wipe_pade2 ####################### # mod p computation #----------------------------------------------------- ####################### diffop_modp In the global factorization the local factorizations are done in characteristic 0. After these local factorizations have been determined they are lifted modulo modulus2^4. These two numbers modulus2 and 4 are increased if something goes wrong (an error "modular inverse does not exist" could occur, the procedure reconstruct could fail, or the reconstructed expression can be incorrect). Also Derksen's pade2 algorithm is done modular. If a global factor is found it is reconstructed to characteristic 0 coefficients. The result of this reconstruction is checked by performing a right division. If it is incorrect the modulus is increased. Global variable: modp_table : in here the values of the Laurent series are stored before a modular computation is started. Procedures: compute_modm(exp,procname,args) : modulus becomes global variable modulus2 to : the power exp. Then it calls procname(args) : with modular computation. If an error occurs : the prime number modulus2 is increased. : Uses compute_modp. compute_modp : Changes computation from non-modular to : modular, does computation, and changes : computation back to non-modular. reconstruct : reconstruct expression from its modular : image ######################## # Various tools #----------------------------------------- ######################## diffop_tools symmetric_power : Symmetric power exterior_power : Exterior power `diffop/_symext` : used by symmetric_power and exterior_power cyclic_vector : Cyclic vector computation `diffop/apply_A` : Apply matrix diff. operator, used by cyclic_vector adjoint : The adjoint, map DF to -DF. Both global and local (xDF -> -xDF). `diffop/lift_adjoint` : Lift procedure for the local (xDF syntax with power series coeffs) adjoint. rational_solutions : rational solutions of a diff operator. GCRD : Greatest Common Right Divisor rightdivision : Division, both local and global. lift_rightdivision : Lift algorithm for the local division leftdivision : Left division, only global. LCLM : Least Common Left Multiple ##################################### # The mixed differential equation #---------------------------------------- ##################################### diffop_mixed_eqn bounds_frlf0 : Bounds for the mixed equation f*r+l*f=0 local_frlf0 : a basis of the local solutions of the mixed equation lift_frlf0 : Lift a local solution to some accuracy. liftstep_frlf0 : Lift a local solution one step. eigenring : Compute the ring of endomorphisms. eigenring_lineq : Find linear equations on r from r(V(f)) subset V(f) endomorphism_charpoly : The characteristic polynomial of r on V(f). #################################### # Global factorizations #------------------------------------------ #################################### diffop_global Procedures: DFactor : Factorization xDFn_modr : Computes xDF^n mod r flist : tool for try_factorization, its output is : the input for pade2 try_factorization : try a local factor for a global factor try_factorization2 : tool for try_factorization factor_global : Output: [f] or f factored in 2 factors. factor_minmult1 : used by factor_global. This procedure treats the case minimum multiplicity 1. The output is a list of 2 factors, or [f]. In this latter case f is irreducible. factor_order1 : additional code used by factor_global to complete the algorithm for the case where there are 1st order factors. compute_bound : Bound for the number of extra (apparant) singularities in 1st order factors. ######################### # global variables #----------------------------------------------------- ######################### diffop_global_vars `diffop/back_up` : Back up all the global variables. The purpose is to be able to restore these variables after a ctrl-c. This is not really used yet in that way.