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) or Float64 (double precision). Calable functions as described are with T as Float64, but variants (with the additional suffix _s, e.g., roots_initialize_s) are available with T as Float32.

callable functions#

    function roots_initialize(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(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(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