solve.h File Reference

General routines ported from MPSolve 2.2. More...

Go to the source code of this file.

Functions
MPS_BEGIN_DECLS void	mps_update (mps_context *s)
	Set again[i] to true or to false according to the values of status and inclusion in the mps_approximation and the current goal.
void	mps_fsrad (mps_context *s, mps_cluster *cluster, cplx_t sc, double *sr)
	Compute super center and super radius.
void	mps_dsrad (mps_context *s, mps_cluster *cluster, cdpe_t sc, rdpe_t sr)
	dpe version of fsrad()
void	mps_msrad (mps_context *s, mps_cluster *cluster, mpc_t sc, rdpe_t sr)
	Multiprecision versione of fsrad().
mps_boolean	mps_check_stop (mps_context *s)
	Check if the roots are computed with the required precision.
void	mps_fsolve (mps_context *s, mps_boolean *d_after_f)
	Actually solve the polynomial.
void	mps_dsolve (mps_context *s, mps_boolean d_after_f)
	dpe version of fsolve().
void	mps_msolve (mps_context *s)
	Multiprecision version of fsolve().
void	mps_fpolzer (mps_context *s, int *it, mps_boolean *excep)
	This routine applies nit iterations of Aberth's method.
void	mps_dpolzer (mps_context *s, int *it, mps_boolean *excep)
	dpe version of fpolzer().
void	mps_mpolzer (mps_context *s, int *it, mps_boolean *excep)
	Multiprecision versione of fpolzer().
void	mps_fmodify (mps_context *s, mps_boolean track_new_cluster)
	Modify the vector 'status' according to the goal, and to the location of the roots.
void	mps_dmodify (mps_context *s, mps_boolean track_new_cluster)
	The DPE version of mps_fmodify().
void	mps_mmodify (mps_context *s, mps_boolean track_new_cluster)
	The multiprecision version of the routine mps_fmodify().
void	mps_fupdate_inclusions (mps_context *s)
	Check if the target set has been reached or not, and update the field s->root_inclusion[i] for every root.
void	mps_dupdate_inclusions (mps_context *s)
	Check if the target set has been reached or not, and update the field s->root[i]->inclusion for every root.
void	mps_mupdate_inclusions (mps_context *s)
	Check if the target set has been reached or not, and update the field s->root[i]->inclusion for every root.
mps_boolean	mps_inclusion (mps_context *s)
	Check the validity of the inclusions disks.

Detailed Description

General routines ported from MPSolve 2.2.

Function Documentation

mps_check_stop()

mps_boolean mps_check_stop

(

mps_context *

s

)

Check if the roots are computed with the required precision.

Set computed to true if the stop condition is satisfied, otherwise set computed to false.

The stop condition is obtained from the vector status as follows:

If the goal is count stop if

• **u does not exist, except for a*u, o*u, f*u
• Mult. and does not exist c**
• Real. and does not exist u, except for au*, ou*;
• Imag and does not exist v, except for av*, ov*;

If the goal is isolate or approximate stop if:

• **u does not exist, except for a*u, o*u, f*u and if c*i does not exist;
• Mult. and does not exist c*i, o*i
• Real. and does not exist *ui, except for aui, oui;
• Imag and does not exist *vi, except for avi, ovi;

See also

status

mps_dmodify()

void mps_dmodify	(	mps_context *	s,
		mps_boolean	track_new_cluster )

The DPE version of mps_fmodify().

Parameters

s	The mps_context associated to the current computation.
track_new_cluster	true if old clusters should be marked with 'C' instead of 'c', so they are recognizable (for shifting).

See also

mps_fmodify()

mps_fmodify()

void mps_fmodify	(	mps_context *	s,
		mps_boolean	track_new_cluster )

Modify the vector 'status' according to the goal, and to the location of the roots.

Parameters

s	The mps_context associated to the current computation.
track_new_cluster	true if old clusters should be marked with 'C' instead of 'c', so they are recognizable (for shifting).

The subroutine is used also for marking the new cluster that have been detected between two consecutive packets of Aberth's iteration.

1. The subroutine changes into 'C' the components of status[:1) corresponding to old clusters, keeping status[:,1)='c' for the new formed clusters. In this way applying restart selects new starting approximations only for the new detected clusters.
2. For the components for which status[:,1]!='C', 'f', 'x' performs the following analysis: If the cluster has mult=1 mark it with status[:1)='i' if is also approximated mark it with status(:1)='a' Check if c*u and i*u (i.e., uncertain set) can be made certain according to goal[1]
3. Perform the same with options, that is, If multiplicity is on then check if a cluster corresponds to a multiple root If detect real then detect real roots if detect imaginary then detect imaginary roots If detect both then detect both imaginary and real roots

mps_fpolzer()

void mps_fpolzer	(	mps_context *	s,
		int *	it,
		mps_boolean *	excep )

This routine applies nit iterations of Aberth's method.

The method is applied to the i-th component of the approximations for which again[i] is true. Set again[i]=false if the i-th approximation is in the root neighbourhood. Stop if again[i]=false for any i.

Parameters

s	The mps_context associated with the current computation.
it	Index of the component on which the iteration is needed.
excep	This variable is set to true if after nit iterations some approximation is still out of the root neighbourhood.

mps_fsolve()

void mps_fsolve	(	mps_context *	s,
		mps_boolean *	d_after_f )

Actually solve the polynomial.

This routine performs the following computations:

1. Select starting approximations and check if some of them need dpe. Initialize the vector again which is true if the corresponding approximation is out of the root neighbourhood.
2. Performs max_pack packets of Aberth iterations on all the components out of the root neighbourhood belonging to the set S and on which it is possible to iterate with float. More precisely, each packet performs max_it iterations on all the components where again is true. At each iteration check if the current approximation is in the root neighbourhood; in this case set 'again' to false.
3. If at the end of the general packet all the approximations are inside the root neighbourhood, i.e., 'again' is false in all the components then return. else, perform cluster analysis, select new starting approximations update the vector 'statu', update the vector 'again' that selects the components on which to iterate, according to the goal, and repeat until the max number of allowed packets is reached. In the latter case output FAILURE.

The local variable again controls the iteration: i.e., again[i]=true means iterate on the i-th component

Parameters

s	The mps_context associated with the current computation.
d_after_f	this variable is true if dpe are needed after the floating point pass.

mps_fsrad()

void mps_fsrad	(	mps_context *	s,
		mps_cluster *	cluster,
		cplx_t	sc,
		double *	sr )

Compute super center and super radius.

This routines the super radius of the i-th cluster, i.e. the radius of the inclusion disc for the whole cluster

Parameters

s	The mps_context associated with the current computation.
cluster	cluster of which the super center and radius should be computed.
sc	Center of the cluster;
sr	Double that will be set to the super radius of the cluster;

mps_inclusion()

mps_boolean mps_inclusion

(

mps_context *

s

)

Check the validity of the inclusions disks.

Parameters

s	A pointer to the current mps_context.

mps_mmodify()

void mps_mmodify	(	mps_context *	s,
		mps_boolean	track_new_cluster )

The multiprecision version of the routine mps_fmodify().

Parameters

s	The mps_context associated to the current computation.
track_new_cluster	true if old clusters should be marked with 'C' instead of 'c', so they are recognizable (for shifting).

See also

mps_fmodify()

mps_update()

MPS_BEGIN_DECLS void mps_update

(

mps_context *

s

)

Set again[i] to true or to false according to the values of status and inclusion in the mps_approximation and the current goal.

More precisely:

• If goal is MPS_OUTPUT_GOAL_COUNT: true only if inclusion is MPS_ROOT_INCLUSION_UNKNOWN and status is not MPS_ROOT_STATUS_APPROXIMATED, MPS_ROOT_STATUS_APPROXIMATED_IN_CLUSTER or MPS_ROOT_STATUS_NOT_FLOAT.
• If goal is MPS_OUTPUT_GOAL_ISOLATE or MPS_OUTPUT_GOAL_APPROXIMATE: true if status is MPS_ROOT_STATUS_CLUSTERED or inclusion is MPS_ROOT_INCLUSION_UNKNOWN.