GALAHAD ROOTS package

purpose

The roots package uses classical formulae together with Newton’s method to find all the real roots of a real polynomial.

Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!

See Section 4 of $GALAHAD/doc/roots.pdf for additional details.

method

Littlewood and Ferrari’s algorithms are used to find estimates of the real roots of cubic and quartic polynomials, respectively; a stabilized version of the well-known formula is used in the quadratic case. Newton’s method and/or methods based on the companion matrix are used to further refine the computed roots if necessary. Madsen and Reid’s (1975) method is used for polynomials whose degree exceeds four.

reference

The basic method is that given by

K. Madsen and J. K. Reid, ``FORTRAN Subroutines for Finding Polynomial Zeros’’. Technical Report A.E.R.E. R.7986, Computer Science and System Division, A.E.R.E. Harwell, Oxfordshire (1975)

parametric real type T

Below, the symbol T refers to a parametric real type that may be Float32 (single precision), Float64 (double precision) or, if supported, Float128 (quadruple precision).

callable functions

    function roots_initialize(T, data, control, status)

Set default control values and initialize private data

Parameters:

data	holds private internal data
control	is a structure containing control information (see roots_control_type)
status	is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently): 0 The initialization was successful.

    function roots_information(T, data, inform, status)

Provides output information

Parameters:

data	holds private internal data
inform	is a structure containing output information (see roots_inform_type)
status	is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently): 0 The values were recorded successfully

    function roots_terminate(T, data, control, inform)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a structure containing control information (see roots_control_type)
inform	is a structure containing output information (see roots_inform_type)

available structures

roots_control_type structure

    struct roots_control_type{T}
      f_indexing::Bool
      error::Int32
      out::Int32
      print_level::Int32
      tol::T
      zero_coef::T
      zero_f::T
      space_critical::Bool
      deallocate_error_fatal::Bool
      prefix::NTuple{31,Cchar}

detailed documentation

control derived type as a Julia structure

components

Bool f_indexing

use C or Fortran sparse matrix indexing

Int32 error

error and warning diagnostics occur on stream error

Int32 out

general output occurs on stream out

Int32 print_level

the level of output required is specified by print_level

T tol

the required accuracy of the roots

T zero_coef

any coefficient smaller in absolute value than zero_coef will be regarde to be zero

T zero_f

any value of the polynomial smaller in absolute value than zero_f will be regarded as giving a root

Bool space_critical

if .space_critical true, every effort will be made to use as little space as possible. This may result in longer computation time

Bool deallocate_error_fatal

if .deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue

NTuple{31,Cchar} prefix

all output lines will be prefixed by .prefix(2:LEN(TRIM(.prefix))-1) where .prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

roots_inform_type structure

    struct roots_inform_type
      status::Int32
      alloc_status::Int32
      bad_alloc::NTuple{81,Cchar}

detailed documentation

inform derived type as a Julia structure

components

Int32 status

return status. Possible values are:

• 0

  The call was successful.

• -1

  An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

• -2

  A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.

• -3

  Either the specified degree of the polynomial in degree is less than 0, or the declared dimension of the array roots is smaller than the specified degree.

Int32 alloc_status

the status of the last attempted allocation/deallocation

NTuple{81,Cchar} bad_alloc

the name of the array for which an allocation/deallocation error occurred

Index