MBDyn-1.7.3
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups
colamd.c File Reference
#include <math.h>
#include "colamd.h"
#include <limits.h>
#include <stdio.h>
#include <assert.h>
Include dependency graph for colamd.c:

Go to the source code of this file.

Macros

#define NDEBUG
 
#define PUBLIC
 
#define PRIVATE   static
 
#define MAX(a, b)   (((a) > (b)) ? (a) : (b))
 
#define MIN(a, b)   (((a) < (b)) ? (a) : (b))
 
#define ONES_COMPLEMENT(r)   (-(r)-1)
 
#define TRUE   (1)
 
#define FALSE   (0)
 
#define EMPTY   (-1)
 
#define ALIVE   (0)
 
#define DEAD   (-1)
 
#define DEAD_PRINCIPAL   (-1)
 
#define DEAD_NON_PRINCIPAL   (-2)
 
#define ROW_IS_DEAD(r)   ROW_IS_MARKED_DEAD (Row[r].shared2.mark)
 
#define ROW_IS_MARKED_DEAD(row_mark)   (row_mark < ALIVE)
 
#define ROW_IS_ALIVE(r)   (Row [r].shared2.mark >= ALIVE)
 
#define COL_IS_DEAD(c)   (Col [c].start < ALIVE)
 
#define COL_IS_ALIVE(c)   (Col [c].start >= ALIVE)
 
#define COL_IS_DEAD_PRINCIPAL(c)   (Col [c].start == DEAD_PRINCIPAL)
 
#define KILL_ROW(r)   { Row [r].shared2.mark = DEAD ; }
 
#define KILL_PRINCIPAL_COL(c)   { Col [c].start = DEAD_PRINCIPAL ; }
 
#define KILL_NON_PRINCIPAL_COL(c)   { Col [c].start = DEAD_NON_PRINCIPAL ; }
 
#define PRINTF   printf
 
#define INDEX(i)   (i)
 
#define DEBUG0(params)   ;
 
#define DEBUG1(params)   ;
 
#define DEBUG2(params)   ;
 
#define DEBUG3(params)   ;
 
#define DEBUG4(params)   ;
 
#define ASSERT(expression)   ((void) 0)
 

Typedefs

typedef long int integer
 
typedef double doublereal
 

Functions

static integer init_rows_cols (integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer p[], integer stats[20])
 
static void init_scoring (integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer head[], double knobs[20], integer *p_n_row2, integer *p_n_col2, integer *p_max_deg)
 
static integer find_ordering (integer n_row, integer n_col, integer Alen, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer head[], integer n_col2, integer max_deg, integer pfree)
 
static void order_children (integer n_col, mbdyn_Colamd_Col Col[], integer p[])
 
static void detect_super_cols (mbdyn_Colamd_Col Col[], integer A[], integer head[], integer row_start, integer row_length)
 
static integer garbage_collection (integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer *pfree)
 
static integer clear_mark (integer n_row, mbdyn_Colamd_Row Row[])
 
static void print_report (char *method, integer stats[20])
 
integer mbdyn_colamd_recommended (integer nnz, integer n_row, integer n_col)
 
void mbdyn_colamd_set_defaults (double knobs[20])
 
integer mbdyn_symamd (integer n, integer A[], integer p[], integer perm[], double knobs[20], integer stats[20], void *(*allocate)(size_t, size_t), void(*release)(void *))
 
integer mbdyn_colamd (integer n_row, integer n_col, integer Alen, integer A[], integer p[], double knobs[20], integer stats[20])
 
void mbdyn_colamd_report (integer stats[20])
 
void mbdyn_symamd_report (integer stats[20])
 

Macro Definition Documentation

#define ALIVE   (0)

Definition at line 771 of file colamd.c.

#define ASSERT (   expression)    ((void) 0)

Definition at line 977 of file colamd.c.

Referenced by FileName::_sPutExt(), OutputHandler::Abstract(), Accumulator::Accumulator(), Actuator::Actuator(), STLVectorHandler::Add(), VectorHandler::Add(), VecN::Add(), MyVectorHandler::Add(), Mat3xN::Add(), FullMatrixHandler::Add(), MatNx3::Add(), MatNxN::Add(), Mat6x6::AddMat(), Mat3xN::AddMat3x3(), InducedVelocity::AddSectionalForce(), FullMatrixHandler::AddT(), NonlinearSolver::AddTimeCPU(), Vec3::AddTo(), FullSubMatrixHandler::AddTo(), Mat3x3::AddTo(), SparseSubMatrixHandler::AddTo(), FullSubMatrixHandler::AddToT(), SparseSubMatrixHandler::AddToT(), CompactSparseMatrixHandler::AddUnchecked(), Mat3xN::AddVec(), MatNx3::AddVec(), Mat3x3::AddVec(), ThirdOrderIntegrator::Advance(), DerivativeSolver::Advance(), Step1Integrator::Advance(), Step2Integrator::Advance(), InverseDynamicsStepSolver::Advance(), OutputHandler::Aerodynamic(), Aerodynamic2DElem< iNN >::Aerodynamic2DElem(), AerodynamicBeam::AerodynamicBeam(), AerodynamicBeam2::AerodynamicBeam2(), AerodynamicBody::AerodynamicBody(), AerodynamicModal::AerodynamicModal(), OutputHandler::AeroModals(), NestedElem::AfterConvergence(), DrivenElem::AfterConvergence(), InducedVelocity::AfterConvergence(), LoadableElem::AfterConvergence(), ConstitutiveLawOwner< T, Tder >::AfterConvergence(), DiscreteControlElem::AfterConvergence(), DataManager::AfterConvergence(), DynamicStructDispNode::AfterConvergence(), DynamicStructNode::AfterConvergence(), DrivenElem::AfterPredict(), NestedElem::AfterPredict(), LoadableElem::AfterPredict(), OutputHandler::AirProps(), MatrixScale< T >::Allocate(), NamedValue::AllocName(), amul(), angle(), anglerel(), AngularAccelerationJoint::AngularAccelerationJoint(), angvel(), angvrel(), ArrayTplDriveCaller< T >::ArrayTplDriveCaller(), ArrayTplDriveCaller< doublereal >::ArrayTplDriveCaller(), DataManager::AssConstrJac(), DataManager::AssConstrRes(), DistanceJoint::AssJac(), DrivenElem::AssJac(), NestedElem::AssJac(), ThreeWayMinorLoss::AssJac(), RodBezier::AssJac(), Rod::AssJac(), ModuleNonsmoothNode::AssJac(), DistanceJointWithOffset::AssJac(), ElasticAxialJoint::AssJac(), ElasticDispJoint::AssJac(), ElasticHingeJoint::AssJac(), LoadableElem::AssJac(), ElasticJoint::AssJac(), Beam2::AssJac(), DataManager::AssJac(), LoadIncForce::AssJac(), DrivenElem::AssMats(), NestedElem::AssMats(), LoadableElem::AssMats(), DataManager::AssMats(), InLineJoint::AssRes(), DistanceJoint::AssRes(), UniversalHingeJoint::AssRes(), PrismaticJoint::AssRes(), SphericalHingeJoint::AssRes(), InPlaneJoint::AssRes(), DrivenElem::AssRes(), StructMappingExtForce::AssRes(), GenelDistance::AssRes(), NestedElem::AssRes(), RodBezier::AssRes(), PlaneHingeJoint::AssRes(), ViscousBody::AssRes(), DynamicMass::AssRes(), DynamicVariableBody::AssRes(), Rod::AssRes(), InLineWithOffsetJoint::AssRes(), TotalEquation::AssRes(), TotalJoint::AssRes(), DistanceJointWithOffset::AssRes(), UniversalRotationJoint::AssRes(), PinJoint::AssRes(), AeroDynModule::AssRes(), DeformableJoint::AssRes(), ElasticAxialJoint::AssRes(), ElasticDispJoint::AssRes(), StaticMass::AssRes(), ElasticHingeJoint::AssRes(), StaticVariableBody::AssRes(), LoadableElem::AssRes(), Beam2::AssRes(), UniversalPinJoint::AssRes(), PlaneRotationJoint::AssRes(), Modal::AssRes(), ClampJoint::AssRes(), ElasticDispJointInv::AssRes(), ViscousAxialJoint::AssRes(), DynamicBody::AssRes(), TotalPinJoint::AssRes(), ViscousHingeJoint::AssRes(), ViscousDispJoint::AssRes(), ViscoElasticAxialJoint::AssRes(), ModalBody::AssRes(), AxialRotationJoint::AssRes(), StaticBody::AssRes(), ViscoElasticDispJoint::AssRes(), TotalForce::AssRes(), LoadIncForce::AssRes(), PlanePinJoint::AssRes(), ViscoElasticHingeJoint::AssRes(), DriveDisplacementJoint::AssVec(), DriveHingeJoint::AssVec(), GenericAerodynamicForce::AssVec(), DriveDisplacementPinJoint::AssVec(), SparseSubMatrixHandler::Attach(), AutomaticStructElem::AutomaticStructElem(), NaiveSparsePermSolutionManager< T >::BackPerm(), Beam::Beam(), Beam2::Beam2(), OutputHandler::Beams(), BeamSliderJoint::BeamSliderJoint(), DrivenElem::BeforePredict(), NestedElem::BeforePredict(), LoadableElem::BeforePredict(), VecIter< Elem * >::bGetCurr(), VecIter< Elem * >::bGetFirst(), VecIter< Elem * >::bGetNext(), StrainGageParam::Bind(), NestedElem::bInverseDynamics(), DriveArrayCaller::bIsDifferentiable(), BiStopCLWrapper< T, Tder >::BiStopCLWrapper(), NonlinearSolverTestRange::bIsValid(), bmul(), Body::Body(), BufferStreamDrive_base::BufferStreamDrive_base(), c81_data_merge(), C81AeroData::C81AeroData(), C81InterpolatedAeroData::C81InterpolatedAeroData(), C81MultipleAeroData::C81MultipleAeroData(), MinMaxDriveDCR::c_str(), DataManager::Cast(), Solver::CheckTimeStepLimit(), IncludeParser::Close(), CenterOfMass::Collect_int(), SchurMatrixHandler::CompNewf(), SchurMatrixHandlerUm::CompNewf(), SchurMatrixHandler::CompNewg(), AutomaticStructElem::ComputeAccelerations(), IterativeMatrixScale< T >::ComputeScaleFactors(), MatrixHandler::ConditionNumber(), ConstitutiveLawOwner< T, Tder >::ConstitutiveLawOwner(), ContactJoint::ContactJoint(), Control_valve::Control_valve(), Control_valve2::Control_valve2(), DataManager::ConvergedSet(), VecN::Copy(), MatNxN::Copy(), FullMatrixHandler::CopyMatrixBlock(), FullMatrixHandler::CopyMatrixRow(), VecN::Create_(), Mat3xN::Create_(), MatNx3::Create_(), MatNxN::Create_(), FullMatrixHandler::CreateColRow(), IdentProcess::CreateIdent(), d_get_priv_data(), DAC_Process_Debug::DAC_Process_Debug(), STLVectorHandler::DecCoef(), MyVectorHandler::DecCoef(), FullMatrixHandler::DecCoef(), SparseSubMatrixHandler::DecCoef(), DeformableAxialJoint::DeformableAxialJoint(), DeformableDispJoint::DeformableDispJoint(), DeformableHingeJoint::DeformableHingeJoint(), DeformableJoint::DeformableJoint(), NestedElem::DescribeDof(), Node::DescribeDof(), TotalJoint::DescribeDof(), ConstitutiveLaw< doublereal, doublereal >::DescribeDof(), Elem::DescribeDof(), ModLugreFriction::DescribeDof(), Aerodynamic2DElem< iNN >::DescribeDof(), DiscreteCoulombFriction::DescribeDof(), ConstitutiveLawOwner< T, Tder >::DescribeDof(), TotalPinJoint::DescribeDof(), NestedElem::DescribeEq(), Node::DescribeEq(), TotalJoint::DescribeEq(), Elem::DescribeEq(), ConstitutiveLaw< doublereal, doublereal >::DescribeEq(), ModLugreFriction::DescribeEq(), Aerodynamic2DElem< iNN >::DescribeEq(), DiscreteCoulombFriction::DescribeEq(), ConstitutiveLawOwner< T, Tder >::DescribeEq(), TotalPinJoint::DescribeEq(), detect_super_cols(), FileDrive::dGet(), MultiStepDrive::dGet(), VecN::dGet(), Vec6::dGet(), Mat3xN::dGet(), Vec3::dGet(), MatNx3::dGet(), Mat6x6::dGet(), MatNxN::dGet(), Mat3x3::dGet(), DriveArrayCaller::dGet(), STLVectorHandler::dGetCoef(), MyVectorHandler::dGetCoef(), FullMatrixHandler::dGetCoef(), SparseSubMatrixHandler::dGetCoef(), AeroDynModule::dGetCurrBladeNodeBuiltinTwist(), AeroDynModule::dGetCurrBladeNodePITNOW(), GaussDataIterator::dGetCurrPnt(), NumIntIterator::dGetCurrPnt(), GaussDataIterator::dGetCurrWght(), NumIntIterator::dGetCurrWght(), Elem2Param::dGetDofValue(), StrainGageParam::dGetDofValue(), StructDispNode::dGetDofValue(), ScalarDifferentialNode::dGetDofValue(), ScalarAlgebraicNode::dGetDofValue(), DynamicStructDispNode::dGetDofValue(), StructNode::dGetDofValue(), DynamicStructNode::dGetDofValue(), StructDispNode::dGetDofValuePrev(), ScalarDifferentialNode::dGetDofValuePrev(), ScalarAlgebraicNode::dGetDofValuePrev(), DynamicStructDispNode::dGetDofValuePrev(), StructNode::dGetDofValuePrev(), DynamicStructNode::dGetDofValuePrev(), GaussDataIterator::dGetFirst(), NumIntIterator::dGetFirst(), IdentProcess::dGetForgettingFactor(), NestedElem::dGetM(), Factor::dGetNewStepTime(), DriveArrayCaller::dGetP(), Motor::dGetPhiElectric(), GaussData::dGetPnt(), TrapezoidData::dGetPnt(), HydraulicFluid::dGetPres0(), ModuleIMU::dGetPrivData(), LinearVelocityJoint::dGetPrivData(), ViscousBody::dGetPrivData(), DistanceJoint::dGetPrivData(), InducedVelocity::dGetPrivData(), DeformableAxialJoint::dGetPrivData(), DeformableDispJoint::dGetPrivData(), DeformableJoint::dGetPrivData(), DeformableHingeJoint::dGetPrivData(), Brake::dGetPrivData(), DriveDisplacementJoint::dGetPrivData(), DriveHingeJoint::dGetPrivData(), RodBezier::dGetPrivData(), PlaneHingeJoint::dGetPrivData(), Rod::dGetPrivData(), AngularVelocityJoint::dGetPrivData(), DistanceJointWithOffset::dGetPrivData(), TotalEquation::dGetPrivData(), TotalJoint::dGetPrivData(), HBeam::dGetPrivData(), StructDispNode::dGetPrivData(), LoadableElem::dGetPrivData(), DriveDisplacementPinJoint::dGetPrivData(), PlaneRotationJoint::dGetPrivData(), Beam2::dGetPrivData(), Wheel4::dGetPrivData(), Modal::dGetPrivData(), TotalReaction::dGetPrivData(), TimeStep::dGetPrivData(), Beam::dGetPrivData(), ViscoElasticBeam2::dGetPrivData(), TotalPinJoint::dGetPrivData(), AxialRotationJoint::dGetPrivData(), ViscoElasticBeam::dGetPrivData(), ShockAbsorberConstitutiveLaw< doublereal, doublereal >::dGetPrivData(), PlanePinJoint::dGetPrivData(), StructNode::dGetPrivData(), DeformableHingeJoint::dGetPrivDataInv(), HydraulicFluid::dGetTemp0(), DriveHandler::dGetTime(), NonlinearSolver::dGetTimeCPU(), DriveHandler::dGetTimeStep(), GaussData::dGetWght(), TrapezoidData::dGetWght(), DiscreteControlARXProcess_Debug::DiscreteControlARXProcess_Debug(), DiscreteControlElem::DiscreteControlElem(), DiscreteIdentProcess_Debug::DiscreteIdentProcess_Debug(), DispMeasure::DispMeasure(), distance(), DistanceJointWithOffset::DistanceJointWithOffset(), DataManager::DofOwnerInit(), DofOwnerOwner::DofOwnerOwner(), DofPlugIn::DofPlugIn(), OutputHandler::DofStats(), drive(), DriveArrayCaller::DriveArrayCaller(), OutputHandler::DriveCallers(), DriveDisplacementJoint::DriveDisplacementJoint(), DriveDisplacementPinJoint::DriveDisplacementPinJoint(), DriveHingeJoint::DriveHingeJoint(), DrivenElem::DrivenElem(), Beam::DsDxi(), DummyPlugIn::DummyPlugIn(), DummyStructNode::DummyStructNode(), Dynamic_control_valve::Dynamic_control_valve(), Dynamic_pipe::Dynamic_pipe(), DynamicForgettingFactor::DynamicForgettingFactor(), DynamicForgettingFactor2::DynamicForgettingFactor2(), DynamicPipe::DynamicPipe(), EE_Eval(), OutputHandler::Eigenanalysis(), OutputHandler::Electric(), DataManager::ElemAssInit(), DataManager::ElemOutputPrepare(), EE_Modulus::Eval(), EE_Divide::Eval(), EE_StmtList::Eval(), ImplicitStepIntegrator::EvalProd(), InverseDynamicsStepSolver::EvalProd(), OutputHandler::Externals(), IncludeParser::fCheckStack(), GaussDataIterator::fGetNext(), NumIntIterator::fGetNext(), FileDrive::FileDrive(), FileDriveCaller::FileDriveCaller(), find_ordering(), FixedStepFileDrive::FixedStepFileDrive(), Flow_valve::Flow_valve(), OutputHandler::Forces(), ForgettingFactor::ForgettingFactor(), FourierSeriesDriveCaller::FourierSeriesDriveCaller(), FreqSweepDriveCaller::FreqSweepDriveCaller(), FullMatrixHandler::FullMatrixHandler(), FullSubMatrixHandler::FullSubMatrixHandler(), garbage_collection(), GaussData::GaussData(), GenelCrossSpringDamperSupport::GenelCrossSpringDamperSupport(), GenelCrossSpringSupport::GenelCrossSpringSupport(), OutputHandler::Genels(), GenelSpringDamperSupport::GenelSpringDamperSupport(), GenelSpringSupport::GenelSpringSupport(), GenelStateSpaceMIMO::GenelStateSpaceMIMO(), GenelStateSpaceSISO::GenelStateSpaceSISO(), Eu2PhiWrap::Get(), GaussData::Get(), TrapezoidData::Get(), OutputHandler::Get(), NestedElem::GetAerodynamicElemType(), NestedElem::GetB_int(), BufferStreamElem::GetBuf(), BufferStreamDrive::GetBuf(), BufferStreamElem::GetBufRaw(), BufferStreamDrive::GetBufRaw(), BufferStreamDriveRaw::GetBufRaw(), Mat3x3::GetCol(), SolverDiagnostics::GetCondMatNorm(), MatrixScaleBase::GetCondNumNorm(), NestedElem::GetConnectedNodes(), LoadableElem::GetConnectedNodes(), DiscreteControlElem::GetConnectedNodes(), AeroDynModule::GetCurrBladeNodeRa(), AeroDynModule::GetCurrBladeR(), DataManager::GetDofDescription(), GenelClamp::GetDofType(), Accelerometer::GetDofType(), InlineFriction::GetDofType(), InLineJoint::GetDofType(), LinearAccelerationJoint::GetDofType(), DistanceJoint::GetDofType(), LinearVelocityJoint::GetDofType(), GenelStateSpaceSISO::GetDofType(), PrismaticJoint::GetDofType(), UniversalHingeJoint::GetDofType(), Pipe::GetDofType(), InPlaneContactJoint::GetDofType(), SphericalHingeJoint::GetDofType(), InPlaneJoint::GetDofType(), GimbalRotationJoint::GetDofType(), ContactJoint::GetDofType(), LoadIncNorm::GetDofType(), Accumulator::GetDofType(), NestedElem::GetDofType(), Brake::GetDofType(), DriveDisplacementJoint::GetDofType(), GenelDistance::GetDofType(), DriveHingeJoint::GetDofType(), TranslAccel::GetDofType(), PlaneHingeJoint::GetDofType(), TotalEquation::GetDofType(), AngularAccelerationJoint::GetDofType(), AerodynamicModal::GetDofType(), TotalJoint::GetDofType(), BeamSliderJoint::GetDofType(), GenelStateSpaceMIMO::GetDofType(), InLineWithOffsetJoint::GetDofType(), Dynamic_pipe::GetDofType(), AngularVelocityJoint::GetDofType(), DistanceJointWithOffset::GetDofType(), Tank::GetDofType(), UniversalRotationJoint::GetDofType(), PinJoint::GetDofType(), RotAccel::GetDofType(), Control_valve2::GetDofType(), InPlaneWithOffsetJoint::GetDofType(), StructDispNode::GetDofType(), Aerodynamic2DElem< iNN >::GetDofType(), Membrane4EAS::GetDofType(), LoadableElem::GetDofType(), DynamicPipe::GetDofType(), DriveDisplacementPinJoint::GetDofType(), PlaneRotationJoint::GetDofType(), UniversalPinJoint::GetDofType(), ClampJoint::GetDofType(), Dynamic_control_valve::GetDofType(), InducedVelocityElem::GetDofType(), Modal::GetDofType(), Shell4EAS::GetDofType(), ScalarDifferentialNode::GetDofType(), TotalReaction::GetDofType(), Shell4EASANS::GetDofType(), ConstitutiveLawOwner< T, Tder >::GetDofType(), ModuleIMUConstraint::GetDofType(), TotalPinJoint::GetDofType(), Pressure_flow_control_valve::GetDofType(), ScalarAlgebraicNode::GetDofType(), AxialRotationJoint::GetDofType(), GenelMass::GetDofType(), Pressure_valve::GetDofType(), Flow_valve::GetDofType(), PlanePinJoint::GetDofType(), Node2Scalar::GetDofType(), DataManager::GetDofType(), NestedElem::GetElemType(), DataManager::GetEqDescription(), GenelClamp::GetEqType(), InlineFriction::GetEqType(), GimbalRotationJoint::GetEqType(), LoadIncNorm::GetEqType(), NestedElem::GetEqType(), Membrane4EAS::GetEqType(), DynamicPipe::GetEqType(), ClampJoint::GetEqType(), Modal::GetEqType(), Shell4EAS::GetEqType(), Shell4EASANS::GetEqType(), DataManager::GetEqType(), BeamConn::Getf(), ConstitutiveLawOwner< T, Tder >::GetF(), ConstitutiveLawOwner< T, Tder >::GetFDE(), ConstitutiveLawOwner< T, Tder >::GetFDEPrime(), C81MultipleAeroData::GetForces(), Vec3::GetFrom(), Mat3x3::GetFrom(), NestedElem::GetG_int(), NaivePermMatrixHandler::GetInvPerm(), NestedElem::GetJ(), NestedElem::GetJ_int(), MathParser::GetLineNumber(), Mat6x6::GetMat(), Mat3xN::GetMat3x3(), Mat3xN::GetMat3x3ScalarMult(), MBDynParser::GetMat6xN(), NamedValue::GetName(), InitialAssemblyIterator::GetNext(), NestedElem::GetNumConnectedNodes(), LoadableElem::GetNumConnectedNodes(), NaivePermMatrixHandler::GetPerm(), Rotor::GetPos(), BeamConn::GetR(), Mat3x3::GetRow(), NestedElem::GetS(), NestedElem::GetS_int(), LinSol::GetSolutionManager(), MathParser::GetToken(), Vec6::GetVec(), Mat3xN::GetVec(), MatNx3::GetVec(), Mat3x3::GetVec(), GimbalRotationJoint::GimbalRotationJoint(), gpc_addmul(), GPC_LAPACK_pinv::GPC_LAPACK_pinv(), gpc_mul(), GPCDesigner::GPCDesigner(), OutputHandler::Gravity(), Gust1D::Gust1D(), HBeam::HBeam(), HopeSolver::HopeSolver(), OutputHandler::Hydraulic(), HydraulicElem::HydraulicElem(), HydrodynamicPlainBearing::HydrodynamicPlainBearing(), DataManager::IDDofInit(), Ident::Ident(), IdentProcess::IdentProcess(), FullSubMatrixHandler::iGetColIndex(), SparseSubMatrixHandler::iGetColIndex(), AeroDynModule::iGetCurrBlade(), AeroDynModule::iGetCurrBladeElem(), NestedElem::iGetFirstIndex(), NestedElem::iGetInitialNumDof(), LoadableElem::iGetInitialNumDof(), NestedElem::iGetNumDof(), ModuleNonsmoothNode::iGetNumDof(), LoadableElem::iGetNumDof(), ConstitutiveLawOwner< T, Tder >::iGetNumDof(), LoadableElem::iGetNumPrivData(), LinearAccelerationJoint::iGetPrivDataIdx(), LinearVelocityJoint::iGetPrivDataIdx(), AircraftInstruments::iGetPrivDataIdx(), ViscousBody::iGetPrivDataIdx(), DistanceJoint::iGetPrivDataIdx(), InducedVelocity::iGetPrivDataIdx(), DeformableAxialJoint::iGetPrivDataIdx(), DeformableDispJoint::iGetPrivDataIdx(), DeformableJoint::iGetPrivDataIdx(), Brake::iGetPrivDataIdx(), DeformableHingeJoint::iGetPrivDataIdx(), DriveDisplacementJoint::iGetPrivDataIdx(), DriveHingeJoint::iGetPrivDataIdx(), RodBezier::iGetPrivDataIdx(), AngularAccelerationJoint::iGetPrivDataIdx(), PlaneHingeJoint::iGetPrivDataIdx(), AirProperties::iGetPrivDataIdx(), Rod::iGetPrivDataIdx(), AngularVelocityJoint::iGetPrivDataIdx(), DistanceJointWithOffset::iGetPrivDataIdx(), TotalEquation::iGetPrivDataIdx(), TotalJoint::iGetPrivDataIdx(), HBeam::iGetPrivDataIdx(), LoadableElem::iGetPrivDataIdx(), DriveDisplacementPinJoint::iGetPrivDataIdx(), PlaneRotationJoint::iGetPrivDataIdx(), Wheel4::iGetPrivDataIdx(), Modal::iGetPrivDataIdx(), ClampJoint::iGetPrivDataIdx(), ScalarDifferentialNode::iGetPrivDataIdx(), TotalReaction::iGetPrivDataIdx(), TimeStep::iGetPrivDataIdx(), Beam::iGetPrivDataIdx(), TotalPinJoint::iGetPrivDataIdx(), ScalarAlgebraicNode::iGetPrivDataIdx(), AxialRotationJoint::iGetPrivDataIdx(), ShockAbsorberConstitutiveLaw< doublereal, doublereal >::iGetPrivDataIdx(), PlanePinJoint::iGetPrivDataIdx(), Beam::iGetPrivDataIdx_int(), FullSubMatrixHandler::iGetRowIndex(), SparseSubMatrixHandler::iGetRowIndex(), MySubVectorHandler::iGetRowIndex(), DriveHandler::iGetStep(), DataManager::iIDGetTotNumDofs(), FileName::iInit(), STLVectorHandler::IncCoef(), MyVectorHandler::IncCoef(), FullMatrixHandler::IncCoef(), SparseSubMatrixHandler::IncCoef(), IncludeParser::IncludeParser(), OutputHandler::Inertia(), RTAISolver::Init(), VecIter< Elem * >::Init(), UniformRotor::Init(), GlauertRotor::Init(), ManglerRotor::Init(), DynamicInflowRotor::Init(), PetersHeRotor::Init(), init_rows_cols(), init_scoring(), InitialAssemblyIterator::InitialAssemblyIterator(), ModuleTemplate::InitialAssJac(), ModuleMDS::InitialAssJac(), ModuleIMU::InitialAssJac(), DistanceJoint::InitialAssJac(), LoadIncNorm::InitialAssJac(), ModuleFMU::InitialAssJac(), CyclocopterInflow::InitialAssJac(), ModuleNonsmoothNode::InitialAssJac(), DistanceJointWithOffset::InitialAssJac(), AeroDynModule::InitialAssJac(), NestedElem::InitialAssJac(), LoadableElem::InitialAssJac(), Wheel4::InitialAssJac(), ModuleIMUConstraint::InitialAssJac(), TimeStep::InitialAssJac(), LoadIncForce::InitialAssJac(), ModuleTemplate::InitialAssRes(), ModuleMDS::InitialAssRes(), ModuleIMU::InitialAssRes(), DistanceJoint::InitialAssRes(), LoadIncNorm::InitialAssRes(), ModuleFMU::InitialAssRes(), CyclocopterInflow::InitialAssRes(), ModuleNonsmoothNode::InitialAssRes(), AeroDynModule::InitialAssRes(), DistanceJointWithOffset::InitialAssRes(), NestedElem::InitialAssRes(), LoadableElem::InitialAssRes(), Wheel4::InitialAssRes(), ModuleIMUConstraint::InitialAssRes(), TimeStep::InitialAssRes(), LoadIncForce::InitialAssRes(), DataManager::InitialJointAssembly(), NestedElem::InitialWorkSpaceDim(), LoadableElem::InitialWorkSpaceDim(), Rotor::InitParam(), InitSF(), InitUDE(), STLVectorHandler::InnerProd(), VectorHandler::InnerProd(), GPC_LAPACK_pinv::Inv(), Mat3x3::Inv(), is_abs_path(), Mat3x3::IsDiag(), OutputHandler::IsOpen(), IsotropicHardeningConstitutiveLaw< T, Tder >::IsotropicHardeningConstitutiveLaw(), Mat3x3::IsSymmetric(), ThirdOrderIntegrator::Jacobian(), DerivativeSolver::Jacobian(), StepNIntegrator::Jacobian(), InverseDynamicsStepSolver::Jacobian(), OutputHandler::Joints(), LabelSearch(), Mat3x3::LDLSolve(), LinearAccelerationJoint::LinearAccelerationJoint(), LineSearchSolver::LineSearch(), OutputHandler::Loadable(), LoadableElem::LoadableElem(), LoadIncForce::LoadIncForce(), LoadIncNorm::LoadIncNorm(), OutputHandler::Log(), LogarithmicWindProfile::LogarithmicWindProfile(), LogConstitutiveLaw< doublereal, doublereal >::LogConstitutiveLaw(), OutputHandler::LogOpen(), NonlinearSolverTest::MakeTest(), Mass::Mass(), Mat3x3::Mat3x3(), Mat3xN::Mat3xN(), Mat6x6::Mat6x6(), NaiveMatrixHandler::MatMatMul_base(), CompactSparseMatrixHandler_tpl< off >::MatMatMul_base(), NaivePermMatrixHandler::MatMatMul_base(), MatR2vec(), NaiveMatrixHandler::MatTMatMul_base(), CompactSparseMatrixHandler_tpl< off >::MatTMatMul_base(), NaivePermMatrixHandler::MatTMatMul_base(), NaiveMatrixHandler::MatTVecMul_base(), CompactSparseMatrixHandler_tpl< off >::MatTVecMul_base(), FullMatrixHandler::MatTVecMul_base(), NaivePermMatrixHandler::MatTVecMul_base(), NaiveMatrixHandler::MatVecMul_base(), CompactSparseMatrixHandler_tpl< off >::MatVecMul_base(), FullMatrixHandler::MatVecMul_base(), NaivePermMatrixHandler::MatVecMul_base(), mbdyn_make_salt(), mbdyn_parse_arguments(), mbdyn_program(), mbdyn_symamd(), mbedge_eat_field(), mbedge_eat_sep(), MinorLoss::MinorLoss(), Modal::Modal(), OutputHandler::Modal(), ModalExt::ModalExt(), ModalForce::ModalForce(), ModalMappingExt::ModalMappingExt(), model_curr(), model_elem(), model_node(), model_sf(), StreamContentCopyCast::Modify(), mp_acos_t(), mp_acosh_t(), mp_actg(), mp_actg2(), mp_asin_t(), mp_atanh_t(), mp_cast(), mp_ctg(), mp_ctg_t(), mp_ctgh(), mp_ctgh_t(), mp_func_1(), mp_func_2(), mp_greater_than_0_t(), mp_greater_than_or_equal_to_0_t(), mp_in(), mp_max(), mp_min(), mp_par(), mp_print(), mp_ramp(), mp_rand(), mp_rndm(), mp_sign(), mp_sprintf(), mp_sramp(), mp_srnd(), mp_step(), mp_stop(), mp_tan_t(), VecN::Mult(), Mat3xN::Mult(), MatNxN::Mult(), MultistepSolver::MultistepSolver(), MySubVectorHandler::MySubVectorHandler(), MyVectorHandler::MyVectorHandler(), NaiveMatrixHandler::NaiveMatrixHandler(), NaivePermMatrixHandler::NaivePermMatrixHandler(), NestedElem::NeedsAirProperties(), NestedElem::NestedElem(), DataManager::NodeOutputPrepare(), Beam::Omega0(), STLVectorHandler::operator()(), NaiveMatrixHandler::operator()(), VecN::operator()(), Vec6::operator()(), MyVectorHandler::operator()(), FullMatrixHandler::operator()(), NaivePermMatrixHandler::operator()(), Vec3::operator()(), Mat3xN::operator()(), MatNx3::operator()(), Mat6x6::operator()(), MatNxN::operator()(), Mat3x3::operator()(), SparseSubMatrixHandler::operator()(), Mat3xN::operator*(), STLVectorHandler::operator+=(), VectorHandler::operator+=(), MyVectorHandler::operator+=(), STLVectorHandler::operator-=(), VectorHandler::operator-=(), MyVectorHandler::operator-=(), Vec6::operator/(), VecExp::operator/(), MatExp::operator/(), Vec3::operator/(), Mat6x6::operator/(), Mat3x3::operator/(), Vec3::operator/=(), Mat6x6::operator/=(), Mat3x3::operator/=(), operator<<(), STLVectorHandler::operator=(), MyVectorHandler::operator=(), Vec3::operator[](), order_children(), Orifice::Orifice(), NestedElem::Output(), DrivenElem::Output(), RodBezier::Output(), Rod::Output(), Joint::Output(), OutputHandler::Output(), LoadableElem::Output(), AerodynamicBody::Output(), AerodynamicBeam::Output(), DriveCaller::Output(), AerodynamicBeam2::Output(), DataManager::OutputEigenvectors(), DataManager::OutputEigGeometry(), DataManager::OutputEigOpen(), NestedElem::OutputPrepare(), AbsoluteDispForce::OutputPrepare(), AbsoluteInternalDispForce::OutputPrepare(), AutomaticStructDispElem::OutputPrepare(), Aerodynamic2DElem< iNN >::OutputPrepare(), StructDispNode::OutputPrepare(), Beam2::OutputPrepare(), AbsoluteForce::OutputPrepare(), AutomaticStructElem::OutputPrepare(), Wheel4::OutputPrepare(), FollowerForce::OutputPrepare(), Beam::OutputPrepare(), AbsoluteCouple::OutputPrepare(), DataManager::OutputPrepare(), FollowerCouple::OutputPrepare(), AbsoluteInternalForce::OutputPrepare(), FollowerInternalForce::OutputPrepare(), AbsoluteInternalCouple::OutputPrepare(), FollowerInternalCouple::OutputPrepare(), StructNode::OutputPrepare(), Joint::OutputPrepare_int(), Inertia::OutputPrepare_int(), OutputHandler::Parameters(), OutputHandler::Partition(), OutputHandler::PartitionOpen(), DataManager::pChooseElem(), DriveArrayCaller::pCopy(), FullMatrixHandler::pdGetMat(), FullMatrixHandler::pdGetVec(), SolutionManager::pdSetResVec(), SolutionManager::pdSetSolVec(), DataManager::pFindDrive(), DataManager::pFindElem(), ConstitutiveLawOwner< T, Tder >::pGetConstLaw(), AeroDynModule::pGetCurrBladeNode(), DofOwnerOwner::pGetDofOwner(), NestedElem::pGetDofOwner(), SwitchDriveCaller::pGetDrive(), NestedElem::pGetInducedVelocity(), Mat6x6::pGetMat(), HBeam::pGetNode(), Membrane4EAS::pGetNode(), Beam2::pGetNode(), Shell4EAS::pGetNode(), Beam::pGetNode(), Shell4EASANS::pGetNode(), Solver::pGetStepIntegrator(), Vec6::pGetVec(), PiecewiseConstShape1D::PiecewiseConstShape1D(), PiecewiseLinearDriveCaller::PiecewiseLinearDriveCaller(), PiecewiseLinearShape1D::PiecewiseLinearShape1D(), PiezoActuatorBeam::PiezoActuatorBeam(), PiezoActuatorBeam2::PiezoActuatorBeam2(), PiezoActuatorVEBeam::PiezoActuatorVEBeam(), PiezoActuatorVEBeam2::PiezoActuatorVEBeam2(), Pipe::Pipe(), PivotRelFrameDummyStructNode::PivotRelFrameDummyStructNode(), pLabelSearch(), OutputHandler::Plates(), PointSurfaceContact::PointSurfaceContact(), NodeResForces::Pole(), position(), PowerLawWindProfile::PowerLawWindProfile(), DataManager::ppFindElem(), AeroMemory::Predict(), ThirdOrderIntegrator::Predict(), Step1Integrator::Predict(), Step2Integrator::Predict(), StreamContentMotion::Prepare(), InverseSolver::Prepare(), Solver::Prepare(), OutputHandler::PresNodes(), Pressure_flow_control_valve::Pressure_flow_control_valve(), Pressure_valve::Pressure_valve(), PrismaticJoint::PrismaticJoint(), PrivPlugIn::PrivPlugIn(), STLVectorHandler::Put(), VectorHandler::Put(), VecN::Put(), Vec6::Put(), MyVectorHandler::Put(), Mat3xN::Put(), Vec3::Put(), FullMatrixHandler::Put(), MatNx3::Put(), MatNxN::Put(), Mat6x6::Put(), Mat3x3::Put(), AirPropOwner::PutAirProperties(), NestedElem::PutAirProperties(), STLVectorHandler::PutCoef(), FullMatrixHandler::PutCoef(), MyVectorHandler::PutCoef(), SparseSubMatrixHandler::PutCoef(), FullSubMatrixHandler::PutColIndex(), SparseSubMatrixHandler::PutColIndex(), FullSubMatrixHandler::PutCross(), SparseSubMatrixHandler::PutCross(), FullSubMatrixHandler::PutDiag(), SparseSubMatrixHandler::PutDiag(), GravityOwner::PutGravity(), SparseSubMatrixHandler::PutItem(), MySubVectorHandler::PutItem(), Mat6x6::PutMat(), Mat3xN::PutMat3x3(), SparseSubMatrixHandler::PutMat3x3(), DAC_Process_Debug::PutOutput(), FullSubMatrixHandler::PutRowIndex(), SparseSubMatrixHandler::PutRowIndex(), MySubVectorHandler::PutRowIndex(), FullMatrixHandler::PutT(), Vec6::PutTo(), Vec3::PutTo(), Mat3x3::PutTo(), Mat3xN::PutVec(), MatNx3::PutVec(), Mat3x3::PutVec(), DofPlugIn::Read(), IncludeDR::Read(), RefFrameDR::Read(), ChDirDR::Read(), HFluidDR::Read(), C81DataDR::Read(), ConstLawDR::Read(), MinMaxDriveDCR::Read(), DriveCallerDR::Read(), TplDriveCallerDR::Read(), SFuncDR::Read(), ModuleLoadDR::Read(), SymbolicCLR< T, Tder >::Read(), ReadAerodynamicBeam(), ReadAirstreamData(), ReadBufferStreamDrive(), ReadBufferStreamElem(), DataManager::ReadControl(), InverseSolver::ReadData(), Solver::ReadData(), ReadElectric(), DataManager::ReadElem(), DataManager::ReadElems(), ReadFF(), ReadGenel(), ReadHydraulicElem(), ReadInducedVelocity(), ReadLoadable(), ReadMembraneConstLaw(), ReadModal(), ReadModalExtForce(), ReadModalMappingExtForce(), DataManager::ReadNode(), DataManager::ReadNodes(), ReadOneBufCast(), ReadPX(), ReadRotor(), ReadShape(), ReadShellConstLaw(), ReadStructMappingExtForce(), ReadStructNode(), ReadTimeStepData(), ExtRigidForceEDGE::Recv(), ExtModalForceEDGE::Recv(), StructExtForce::RecvFromFileDes(), StructExtEDGEForce::RecvFromStream(), StructExtForce::RecvFromStream(), ReferenceFrame::ReferenceFrame(), OutputHandler::ReferenceFrames(), Converged::Register(), MathParser::RegisterNameSpace(), RelFrameDummyStructNode::RelFrameDummyStructNode(), MyVectorHandler::Reset(), SparseSubMatrixHandler::Reset(), AerodynamicOutput::ResetIterator(), ResForceSet::ResForceSet(), ThirdOrderIntegrator::Residual(), DerivativeSolver::Residual(), StepNIntegrator::Residual(), InverseDynamicsStepSolver::Residual(), STLVectorHandler::Resize(), VecN::Resize(), Mat3xN::Resize(), FullSubMatrixHandler::Resize(), MatNx3::Resize(), SparseSubMatrixHandler::Resize(), MySubVectorHandler::Resize(), DrivenElem::Restart(), InverseSolver::Restart(), OutputHandler::Restart(), LoadableElem::Restart(), Solver::Restart(), DriveArrayCaller::Restart(), OutputHandler::RestartOpen(), OutputHandler::RestartXSol(), Rod::Rod(), RodBezier::RodBezier(), RodWithOffset::RodWithOffset(), RotAccel::RotAccel(), OutputHandler::Rotors(), RotorTrim::RotorTrim(), RotorTrimBase::RotorTrimBase(), RTAISolver::RTAISolver(), RTMBDynInDrive::RTMBDynInDrive(), RTMBDynOutElem::RTMBDynOutElem(), RTSolverBase::RTSolverBase(), RunMBDyn(), SampleAndHold::SampleAndHold(), STLVectorHandler::ScalarAddMul(), VectorHandler::ScalarAddMul(), MyVectorHandler::ScalarAddMul(), ScalarFunctionOrthotropicCL< T, Tder >::ScalarFunctionOrthotropicCL(), ScalarFuncWindProfile::ScalarFuncWindProfile(), STLVectorHandler::ScalarMul(), VectorHandler::ScalarMul(), MyVectorHandler::ScalarMul(), ScalarPX::ScalarPX(), NaiveSparseSolutionManager::ScaleSolution(), MatrixScaleBase::ScaleVector(), ExtRigidForceEDGE::Send(), ExtModalForceEDGE::Send(), VariableStepFileDrive::ServePending(), TplDriveOwner< Vec6 >::Set(), DriveOwner::Set(), StreamContentCopyCast::Set(), Gust::SetAirProperties(), HopeSolver::SetCoef(), AeroDynModule::SetCurrBladeNodePITNOW(), AerodynamicOutput::SetData(), MBDynParser::SetDataManager(), StructDispNode::SetDofValue(), ScalarDifferentialNode::SetDofValue(), ScalarAlgebraicNode::SetDofValue(), DynamicStructDispNode::SetDofValue(), Node2Scalar::SetDofValue(), StructNode::SetDofValue(), DynamicStructNode::SetDofValue(), NestedElem::SetInitialValue(), LoadableElem::SetInitialValue(), NestedElem::SetOutputFlag(), ToBeOutput::SetOutputFlag(), OutputHandler::SetPrecision(), C81MultipleAeroData::SetSectionData(), C81InterpolatedAeroData::SetSectionData(), DriveHandler::SetTime(), Traceable::SetTraceFlag(), RTAISolver::Setup(), NestedElem::SetValue(), DrivenElem::SetValue(), LoadableElem::SetValue(), ViscoElasticBeam2::SetValue(), ViscoElasticBeam::SetValue(), DriveHandler::SetVar(), OutputHandler::SetWidth(), ShapeFunc2N(), ShapeFunc3N(), ShapeOwner::ShapeOwner(), BiCGStab::Solve(), Gmres::Solve(), NewtonRaphsonSolver::Solve(), LineSearchSolver::Solve(), NaiveSparsePermSolutionManager< T >::Solve(), Mat3x3::Solve(), Solver::Solver(), SparseSubMatrixHandler::SparseSubMatrixHandler(), STAHRAeroData::STAHRAeroData(), Solver::Start(), StdAirProperties::StdAirProperties(), STLVectorHandler::STLVectorHandler(), StreamContentCopyCast::StreamContentCopyCast(), StreamContentMotion::StreamContentMotion(), StreamContentValue::StreamContentValue(), StreamDrive::StreamDrive(), StreamDriveCopyCast::StreamDriveCopyCast(), StreamOutElem::StreamOutElem(), StringDriveCaller::StringDriveCaller(), OutputHandler::StrNodes(), StructExtEDGEForce::StructExtEDGEForce(), StructExtForce::StructExtForce(), StructMappingExtForce::StructMappingExtForce(), StructuralForce::StructuralForce(), StructuralInternalForce::StructuralInternalForce(), STLVectorHandler::Sub(), VectorHandler::Sub(), VecN::Sub(), MyVectorHandler::Sub(), Mat3xN::Sub(), FullMatrixHandler::Sub(), MatNx3::Sub(), MatNxN::Sub(), Vec3::SubFrom(), FullSubMatrixHandler::SubFrom(), SparseSubMatrixHandler::SubFrom(), FullSubMatrixHandler::SubFromT(), SparseSubMatrixHandler::SubFromT(), Mat6x6::SubMat(), Mat3xN::SubMat3x3(), FullMatrixHandler::SubT(), Mat3xN::SubVec(), MatNx3::SubVec(), Mat3x3::SubVec(), SwashPlate::SwashPlate(), Tank::Tank(), NonlinearSolverTestMinMax::TestMerge(), ImplicitStepIntegrator::TestScale(), InverseDynamicsStepSolver::TestScale(), TheodorsenAeroData::TheodorsenAeroData(), OutputHandler::ThermalElements(), OutputHandler::ThermalNodes(), ThreeWayMinorLoss::ThreeWayMinorLoss(), TotalEquation::TotalEquation(), TotalJoint::TotalJoint(), TotalPinJoint::TotalPinJoint(), DriveCaller::Trace(), OutputHandler::Traces(), TranslAccel::TranslAccel(), TypedValue::TypedValue(), unit_convert(), unitvec(), AeroMemory::Update(), ThirdOrderIntegrator::Update(), DrivenElem::Update(), NestedElem::Update(), DerivativeSolver::Update(), StepNIntegrator::Update(), StructDispNode::Update(), LoadableElem::Update(), ConstitutiveLawOwner< T, Tder >::Update(), ClampJoint::Update(), TotalPinJoint::Update(), DataManager::Update(), DynamicStructDispNode::Update(), InverseDynamicsStepSolver::Update(), LogConstitutiveLaw< doublereal, doublereal >::Update(), StructNode::Update(), DynamicStructNode::Update(), OutputHandler::UseDefaultPrecision(), OutputHandler::UseNetCDF(), OutputHandler::UseScientific(), OutputHandler::UseText(), VariableBody::VariableBody(), VariableStepFileDrive::VariableStepFileDrive(), Vec3::Vec3(), VecIter< Elem * >::VecIter(), VecN::VecN(), VectorPX::VectorPX(), velocity(), ViscousBody::ViscousBody(), vrel(), NestedElem::WorkSpaceDim(), ModuleNonsmoothNode::WorkSpaceDim(), LoadableElem::WorkSpaceDim(), Beam::~Beam(), Beam2::~Beam2(), ConstitutiveLawOwner< T, Tder >::~ConstitutiveLawOwner(), DriveArrayCaller::~DriveArrayCaller(), DrivenElem::~DrivenElem(), HBeam::~HBeam(), HighParser::~HighParser(), LoadableElem::~LoadableElem(), Membrane4EAS::~Membrane4EAS(), NamedValue::~NamedValue(), NestedElem::~NestedElem(), PiezoActuatorBeam2::~PiezoActuatorBeam2(), PiezoActuatorVEBeam2::~PiezoActuatorVEBeam2(), ShapeOwner::~ShapeOwner(), Shell4EAS::~Shell4EAS(), and Shell4EASANS::~Shell4EASANS().

#define COL_IS_ALIVE (   c)    (Col [c].start >= ALIVE)

Definition at line 783 of file colamd.c.

Referenced by detect_super_cols(), find_ordering(), garbage_collection(), and init_scoring().

#define COL_IS_DEAD (   c)    (Col [c].start < ALIVE)

Definition at line 782 of file colamd.c.

Referenced by detect_super_cols(), find_ordering(), init_scoring(), and order_children().

#define COL_IS_DEAD_PRINCIPAL (   c)    (Col [c].start == DEAD_PRINCIPAL)

Definition at line 784 of file colamd.c.

Referenced by order_children().

#define DEAD   (-1)

Definition at line 772 of file colamd.c.

#define DEAD_NON_PRINCIPAL   (-2)

Definition at line 776 of file colamd.c.

#define DEAD_PRINCIPAL   (-1)

Definition at line 775 of file colamd.c.

#define DEBUG0 (   params)    ;

Definition at line 971 of file colamd.c.

Referenced by init_rows_cols(), mbdyn_colamd(), and mbdyn_symamd().

#define DEBUG1 (   params)    ;

Definition at line 972 of file colamd.c.

Referenced by find_ordering(), init_rows_cols(), init_scoring(), and mbdyn_symamd().

#define DEBUG2 (   params)    ;

Definition at line 973 of file colamd.c.

Referenced by find_ordering(), garbage_collection(), and init_scoring().

#define DEBUG3 (   params)    ;

Definition at line 974 of file colamd.c.

Referenced by find_ordering(), and garbage_collection().

#define DEBUG4 (   params)    ;

Definition at line 975 of file colamd.c.

Referenced by find_ordering(), and init_scoring().

#define FALSE   (0)

Definition at line 763 of file colamd.c.

Referenced by init_rows_cols(), mbdyn_colamd(), and mbdyn_symamd().

#define INDEX (   i)    (i)

Definition at line 809 of file colamd.c.

Referenced by print_report().

#define KILL_NON_PRINCIPAL_COL (   c)    { Col [c].start = DEAD_NON_PRINCIPAL ; }

Definition at line 787 of file colamd.c.

Referenced by detect_super_cols().

#define KILL_PRINCIPAL_COL (   c)    { Col [c].start = DEAD_PRINCIPAL ; }

Definition at line 786 of file colamd.c.

Referenced by find_ordering(), and init_scoring().

#define KILL_ROW (   r)    { Row [r].shared2.mark = DEAD ; }

Definition at line 785 of file colamd.c.

Referenced by find_ordering(), garbage_collection(), and init_scoring().

#define MAX (   a,
 
)    (((a) > (b)) ? (a) : (b))

Definition at line 749 of file colamd.c.

Referenced by find_ordering(), and init_scoring().

#define MIN (   a,
 
)    (((a) < (b)) ? (a) : (b))

Definition at line 750 of file colamd.c.

Referenced by find_ordering(), and init_scoring().

#define NDEBUG

Definition at line 692 of file colamd.c.

Referenced by find_ordering().

#define ONES_COMPLEMENT (   r)    (-(r)-1)

Definition at line 752 of file colamd.c.

Referenced by garbage_collection().

#define PRINTF   printf

Definition at line 806 of file colamd.c.

Referenced by print_report().

#define PRIVATE   static

Definition at line 747 of file colamd.c.

#define PUBLIC

Definition at line 746 of file colamd.c.

#define ROW_IS_ALIVE (   r)    (Row [r].shared2.mark >= ALIVE)

Definition at line 781 of file colamd.c.

Referenced by clear_mark(), detect_super_cols(), find_ordering(), and garbage_collection().

#define ROW_IS_DEAD (   r)    ROW_IS_MARKED_DEAD (Row[r].shared2.mark)

Definition at line 779 of file colamd.c.

Referenced by find_ordering(), and init_scoring().

#define ROW_IS_MARKED_DEAD (   row_mark)    (row_mark < ALIVE)

Definition at line 780 of file colamd.c.

Referenced by find_ordering().

#define TRUE   (1)

Definition at line 759 of file colamd.c.

Referenced by init_rows_cols(), mbdyn_colamd(), and mbdyn_symamd().

Typedef Documentation

typedef double doublereal

Definition at line 52 of file colamd.c.

typedef long int integer

Definition at line 51 of file colamd.c.

Function Documentation

static integer clear_mark ( integer  n_row,
mbdyn_Colamd_Row  Row[] 
)
static

Definition at line 3064 of file colamd.c.

References ROW_IS_ALIVE.

Referenced by find_ordering().

3070 {
3071  /* === Local variables ================================================== */
3072 
3073  integer r ;
3074 
3075  for (r = 0 ; r < n_row ; r++)
3076  {
3077  if (ROW_IS_ALIVE (r))
3078  {
3079  Row [r].shared2.mark = 0 ;
3080  }
3081  }
3082  return (1) ;
3083 }
union mbdyn_Colamd_Row::@5 shared2
integer mark
Definition: colamd.h:203
#define ROW_IS_ALIVE(r)
Definition: colamd.c:781
long int integer
Definition: colamd.c:51
static void detect_super_cols ( mbdyn_Colamd_Col  Col[],
integer  A[],
integer  head[],
integer  row_start,
integer  row_length 
)
static

Definition at line 2771 of file colamd.c.

References ASSERT, c, COL_IS_ALIVE, COL_IS_DEAD, EMPTY, KILL_NON_PRINCIPAL_COL, and ROW_IS_ALIVE.

Referenced by find_ordering().

2786 {
2787  /* === Local variables ================================================== */
2788 
2789  integer hash ; /* hash value for a column */
2790  integer *rp ; /* pointer to a row */
2791  integer c ; /* a column index */
2792  integer super_c ; /* column index of the column to absorb into */
2793  integer *cp1 ; /* column pointer for column super_c */
2794  integer *cp2 ; /* column pointer for column c */
2795  integer length ; /* length of column super_c */
2796  integer prev_c ; /* column preceding c in hash bucket */
2797  integer i ; /* loop counter */
2798  integer *rp_end ; /* pointer to the end of the row */
2799  integer col ; /* a column index in the row to check */
2800  integer head_column ; /* first column in hash bucket or degree list */
2801  integer first_col ; /* first column in hash bucket */
2802 
2803  /* === Consider each column in the row ================================== */
2804 
2805  rp = &A [row_start] ;
2806  rp_end = rp + row_length ;
2807  while (rp < rp_end)
2808  {
2809  col = *rp++ ;
2810  if (COL_IS_DEAD (col))
2811  {
2812  continue ;
2813  }
2814 
2815  /* get hash number for this column */
2816  hash = Col [col].shared3.hash ;
2817  ASSERT (hash <= n_col) ;
2818 
2819  /* === Get the first column in this hash bucket ===================== */
2820 
2821  head_column = head [hash] ;
2822  if (head_column > EMPTY)
2823  {
2824  first_col = Col [head_column].shared3.headhash ;
2825  }
2826  else
2827  {
2828  first_col = - (head_column + 2) ;
2829  }
2830 
2831  /* === Consider each column in the hash bucket ====================== */
2832 
2833  for (super_c = first_col ; super_c != EMPTY ;
2834  super_c = Col [super_c].shared4.hash_next)
2835  {
2836  ASSERT (COL_IS_ALIVE (super_c)) ;
2837  ASSERT (Col [super_c].shared3.hash == hash) ;
2838  length = Col [super_c].length ;
2839 
2840  /* prev_c is the column preceding column c in the hash bucket */
2841  prev_c = super_c ;
2842 
2843  /* === Compare super_c with all columns after it ================ */
2844 
2845  for (c = Col [super_c].shared4.hash_next ;
2846  c != EMPTY ; c = Col [c].shared4.hash_next)
2847  {
2848  ASSERT (c != super_c) ;
2849  ASSERT (COL_IS_ALIVE (c)) ;
2850  ASSERT (Col [c].shared3.hash == hash) ;
2851 
2852  /* not identical if lengths or scores are different */
2853  if (Col [c].length != length ||
2854  Col [c].shared2.score != Col [super_c].shared2.score)
2855  {
2856  prev_c = c ;
2857  continue ;
2858  }
2859 
2860  /* compare the two columns */
2861  cp1 = &A [Col [super_c].start] ;
2862  cp2 = &A [Col [c].start] ;
2863 
2864  for (i = 0 ; i < length ; i++)
2865  {
2866  /* the columns are "clean" (no dead rows) */
2867  ASSERT (ROW_IS_ALIVE (*cp1)) ;
2868  ASSERT (ROW_IS_ALIVE (*cp2)) ;
2869  /* row indices will same order for both supercols, */
2870  /* no gather scatter nessasary */
2871  if (*cp1++ != *cp2++)
2872  {
2873  break ;
2874  }
2875  }
2876 
2877  /* the two columns are different if the for-loop "broke" */
2878  if (i != length)
2879  {
2880  prev_c = c ;
2881  continue ;
2882  }
2883 
2884  /* === Got it! two columns are identical =================== */
2885 
2886  ASSERT (Col [c].shared2.score == Col [super_c].shared2.score) ;
2887 
2888  Col [super_c].shared1.thickness += Col [c].shared1.thickness ;
2889  Col [c].shared1.parent = super_c ;
2891  /* order c later, in order_children() */
2892  Col [c].shared2.order = EMPTY ;
2893  /* remove c from hash bucket */
2894  Col [prev_c].shared4.hash_next = Col [c].shared4.hash_next ;
2895  }
2896  }
2897 
2898  /* === Empty this hash bucket ======================================= */
2899 
2900  if (head_column > EMPTY)
2901  {
2902  /* corresponding degree list "hash" is not empty */
2903  Col [head_column].shared3.headhash = EMPTY ;
2904  }
2905  else
2906  {
2907  /* corresponding degree list "hash" is empty */
2908  head [hash] = EMPTY ;
2909  }
2910  }
2911 }
integer hash
Definition: colamd.h:180
#define COL_IS_ALIVE(c)
Definition: colamd.c:783
union mbdyn_Colamd_Col::@1 shared2
#define KILL_NON_PRINCIPAL_COL(c)
Definition: colamd.c:787
integer headhash
Definition: colamd.h:178
integer score
Definition: colamd.h:173
#define COL_IS_DEAD(c)
Definition: colamd.c:782
#define ASSERT(expression)
Definition: colamd.c:977
integer hash_next
Definition: colamd.h:187
static std::stack< cleanup * > c
Definition: cleanup.cc:59
union mbdyn_Colamd_Col::@3 shared4
integer length
Definition: colamd.h:163
integer start
Definition: colamd.h:161
#define EMPTY
Definition: colamd.c:768
union mbdyn_Colamd_Col::@2 shared3
#define ROW_IS_ALIVE(r)
Definition: colamd.c:781
long int integer
Definition: colamd.c:51
static integer find_ordering ( integer  n_row,
integer  n_col,
integer  Alen,
mbdyn_Colamd_Row  Row[],
mbdyn_Colamd_Col  Col[],
integer  A[],
integer  head[],
integer  n_col2,
integer  max_deg,
integer  pfree 
)
static

Definition at line 2106 of file colamd.c.

References ASSERT, clear_mark(), COL_IS_ALIVE, COL_IS_DEAD, DEBUG1, DEBUG2, DEBUG3, DEBUG4, detect_super_cols(), EMPTY, garbage_collection(), KILL_PRINCIPAL_COL, KILL_ROW, MAX, MIN, NDEBUG, ROW_IS_ALIVE, ROW_IS_DEAD, and ROW_IS_MARKED_DEAD.

Referenced by mbdyn_colamd().

2120 {
2121  /* === Local variables ================================================== */
2122 
2123  integer k ; /* current pivot ordering step */
2124  integer pivot_col ; /* current pivot column */
2125  integer *cp ; /* a column pointer */
2126  integer *rp ; /* a row pointer */
2127  integer pivot_row ; /* current pivot row */
2128  integer *new_cp ; /* modified column pointer */
2129  integer *new_rp ; /* modified row pointer */
2130  integer pivot_row_start ; /* pointer to start of pivot row */
2131  integer pivot_row_degree ; /* number of columns in pivot row */
2132  integer pivot_row_length ; /* number of supercolumns in pivot row */
2133  integer pivot_col_score ; /* score of pivot column */
2134  integer needed_memory ; /* free space needed for pivot row */
2135  integer *cp_end ; /* pointer to the end of a column */
2136  integer *rp_end ; /* pointer to the end of a row */
2137  integer row ; /* a row index */
2138  integer col ; /* a column index */
2139  integer max_score ; /* maximum possible score */
2140  integer cur_score ; /* score of current column */
2141  unsigned int hash ; /* hash value for supernode detection */
2142  integer head_column ; /* head of hash bucket */
2143  integer first_col ; /* first column in hash bucket */
2144  integer tag_mark ; /* marker value for mark array */
2145  integer row_mark ; /* Row [row].shared2.mark */
2146  integer set_difference ; /* set difference size of row with pivot row */
2147  integer min_score ; /* smallest column score */
2148  integer col_thickness ; /* "thickness" (no. of columns in a supercol) */
2149  integer max_mark ; /* maximum value of tag_mark */
2150  integer pivot_col_thickness ; /* number of columns represented by pivot col */
2151  integer prev_col ; /* Used by Dlist operations. */
2152  integer next_col ; /* Used by Dlist operations. */
2153  integer ngarbage ; /* number of garbage collections performed */
2154 
2155 #ifndef NDEBUG
2156  integer debug_d ; /* debug loop counter */
2157  integer debug_step = 0 ; /* debug loop counter */
2158 #endif /* NDEBUG */
2159 
2160  /* === Initialization and clear mark ==================================== */
2161 
2162  max_mark = INT_MAX - n_col ; /* INT_MAX defined in <limits.h> */
2163  tag_mark = clear_mark (n_row, Row) ;
2164  min_score = 0 ;
2165  ngarbage = 0 ;
2166  DEBUG1 (("colamd: Ordering, n_col2=%d\n", n_col2)) ;
2167 
2168  /* === Order the columns ================================================ */
2169 
2170  for (k = 0 ; k < n_col2 ; /* 'k' is incremented below */)
2171  {
2172 
2173 #ifndef NDEBUG
2174  if (debug_step % 100 == 0)
2175  {
2176  DEBUG2 (("\n... Step k: %d out of n_col2: %d\n", k, n_col2)) ;
2177  }
2178  else
2179  {
2180  DEBUG3 (("\n----------Step k: %d out of n_col2: %d\n", k, n_col2)) ;
2181  }
2182  debug_step++ ;
2183  debug_deg_lists (n_row, n_col, Row, Col, head,
2184  min_score, n_col2-k, max_deg) ;
2185  debug_matrix (n_row, n_col, Row, Col, A) ;
2186 #endif /* NDEBUG */
2187 
2188  /* === Select pivot column, and order it ============================ */
2189 
2190  /* make sure degree list isn't empty */
2191  ASSERT (min_score >= 0) ;
2192  ASSERT (min_score <= n_col) ;
2193  ASSERT (head [min_score] >= EMPTY) ;
2194 
2195 #ifndef NDEBUG
2196  for (debug_d = 0 ; debug_d < min_score ; debug_d++)
2197  {
2198  ASSERT (head [debug_d] == EMPTY) ;
2199  }
2200 #endif /* NDEBUG */
2201 
2202  /* get pivot column from head of minimum degree list */
2203  while (head [min_score] == EMPTY && min_score < n_col)
2204  {
2205  min_score++ ;
2206  }
2207  pivot_col = head [min_score] ;
2208  ASSERT (pivot_col >= 0 && pivot_col <= n_col) ;
2209  next_col = Col [pivot_col].shared4.degree_next ;
2210  head [min_score] = next_col ;
2211  if (next_col != EMPTY)
2212  {
2213  Col [next_col].shared3.prev = EMPTY ;
2214  }
2215 
2216  ASSERT (COL_IS_ALIVE (pivot_col)) ;
2217  DEBUG3 (("Pivot col: %d\n", pivot_col)) ;
2218 
2219  /* remember score for defrag check */
2220  pivot_col_score = Col [pivot_col].shared2.score ;
2221 
2222  /* the pivot column is the kth column in the pivot order */
2223  Col [pivot_col].shared2.order = k ;
2224 
2225  /* increment order count by column thickness */
2226  pivot_col_thickness = Col [pivot_col].shared1.thickness ;
2227  k += pivot_col_thickness ;
2228  ASSERT (pivot_col_thickness > 0) ;
2229 
2230  /* === Garbage_collection, if necessary ============================= */
2231 
2232  needed_memory = MIN (pivot_col_score, n_col - k) ;
2233  if (pfree + needed_memory >= Alen)
2234  {
2235  pfree = garbage_collection (n_row, n_col, Row, Col, A, &A [pfree]) ;
2236  ngarbage++ ;
2237  /* after garbage collection we will have enough */
2238  ASSERT (pfree + needed_memory < Alen) ;
2239  /* garbage collection has wiped out the Row[].shared2.mark array */
2240  tag_mark = clear_mark (n_row, Row) ;
2241 
2242 #ifndef NDEBUG
2243  debug_matrix (n_row, n_col, Row, Col, A) ;
2244 #endif /* NDEBUG */
2245  }
2246 
2247  /* === Compute pivot row pattern ==================================== */
2248 
2249  /* get starting location for this new merged row */
2250  pivot_row_start = pfree ;
2251 
2252  /* initialize new row counts to zero */
2253  pivot_row_degree = 0 ;
2254 
2255  /* tag pivot column as having been visited so it isn't included */
2256  /* in merged pivot row */
2257  Col [pivot_col].shared1.thickness = -pivot_col_thickness ;
2258 
2259  /* pivot row is the union of all rows in the pivot column pattern */
2260  cp = &A [Col [pivot_col].start] ;
2261  cp_end = cp + Col [pivot_col].length ;
2262  while (cp < cp_end)
2263  {
2264  /* get a row */
2265  row = *cp++ ;
2266  DEBUG4 (("Pivot col pattern %d %d\n", ROW_IS_ALIVE (row), row)) ;
2267  /* skip if row is dead */
2268  if (ROW_IS_DEAD (row))
2269  {
2270  continue ;
2271  }
2272  rp = &A [Row [row].start] ;
2273  rp_end = rp + Row [row].length ;
2274  while (rp < rp_end)
2275  {
2276  /* get a column */
2277  col = *rp++ ;
2278  /* add the column, if alive and untagged */
2279  col_thickness = Col [col].shared1.thickness ;
2280  if (col_thickness > 0 && COL_IS_ALIVE (col))
2281  {
2282  /* tag column in pivot row */
2283  Col [col].shared1.thickness = -col_thickness ;
2284  ASSERT (pfree < Alen) ;
2285  /* place column in pivot row */
2286  A [pfree++] = col ;
2287  pivot_row_degree += col_thickness ;
2288  }
2289  }
2290  }
2291 
2292  /* clear tag on pivot column */
2293  Col [pivot_col].shared1.thickness = pivot_col_thickness ;
2294  max_deg = MAX (max_deg, pivot_row_degree) ;
2295 
2296 #ifndef NDEBUG
2297  DEBUG3 (("check2\n")) ;
2298  debug_mark (n_row, Row, tag_mark, max_mark) ;
2299 #endif /* NDEBUG */
2300 
2301  /* === Kill all rows used to construct pivot row ==================== */
2302 
2303  /* also kill pivot row, temporarily */
2304  cp = &A [Col [pivot_col].start] ;
2305  cp_end = cp + Col [pivot_col].length ;
2306  while (cp < cp_end)
2307  {
2308  /* may be killing an already dead row */
2309  row = *cp++ ;
2310  DEBUG3 (("Kill row in pivot col: %d\n", row)) ;
2311  KILL_ROW (row) ;
2312  }
2313 
2314  /* === Select a row index to use as the new pivot row =============== */
2315 
2316  pivot_row_length = pfree - pivot_row_start ;
2317  if (pivot_row_length > 0)
2318  {
2319  /* pick the "pivot" row arbitrarily (first row in col) */
2320  pivot_row = A [Col [pivot_col].start] ;
2321  DEBUG3 (("Pivotal row is %d\n", pivot_row)) ;
2322  }
2323  else
2324  {
2325  /* there is no pivot row, since it is of zero length */
2326  pivot_row = EMPTY ;
2327  ASSERT (pivot_row_length == 0) ;
2328  }
2329  ASSERT (Col [pivot_col].length > 0 || pivot_row_length == 0) ;
2330 
2331  /* === Approximate degree computation =============================== */
2332 
2333  /* Here begins the computation of the approximate degree. The column */
2334  /* score is the sum of the pivot row "length", plus the size of the */
2335  /* set differences of each row in the column minus the pattern of the */
2336  /* pivot row itself. The column ("thickness") itself is also */
2337  /* excluded from the column score (we thus use an approximate */
2338  /* external degree). */
2339 
2340  /* The time taken by the following code (compute set differences, and */
2341  /* add them up) is proportional to the size of the data structure */
2342  /* being scanned - that is, the sum of the sizes of each column in */
2343  /* the pivot row. Thus, the amortized time to compute a column score */
2344  /* is proportional to the size of that column (where size, in this */
2345  /* context, is the column "length", or the number of row indices */
2346  /* in that column). The number of row indices in a column is */
2347  /* monotonically non-decreasing, from the length of the original */
2348  /* column on input to colamd. */
2349 
2350  /* === Compute set differences ====================================== */
2351 
2352  DEBUG3 (("** Computing set differences phase. **\n")) ;
2353 
2354  /* pivot row is currently dead - it will be revived later. */
2355 
2356  DEBUG3 (("Pivot row: ")) ;
2357  /* for each column in pivot row */
2358  rp = &A [pivot_row_start] ;
2359  rp_end = rp + pivot_row_length ;
2360  while (rp < rp_end)
2361  {
2362  col = *rp++ ;
2363  ASSERT (COL_IS_ALIVE (col) && col != pivot_col) ;
2364  DEBUG3 (("Col: %d\n", col)) ;
2365 
2366  /* clear tags used to construct pivot row pattern */
2367  col_thickness = -Col [col].shared1.thickness ;
2368  ASSERT (col_thickness > 0) ;
2369  Col [col].shared1.thickness = col_thickness ;
2370 
2371  /* === Remove column from degree list =========================== */
2372 
2373  cur_score = Col [col].shared2.score ;
2374  prev_col = Col [col].shared3.prev ;
2375  next_col = Col [col].shared4.degree_next ;
2376  ASSERT (cur_score >= 0) ;
2377  ASSERT (cur_score <= n_col) ;
2378  ASSERT (cur_score >= EMPTY) ;
2379  if (prev_col == EMPTY)
2380  {
2381  head [cur_score] = next_col ;
2382  }
2383  else
2384  {
2385  Col [prev_col].shared4.degree_next = next_col ;
2386  }
2387  if (next_col != EMPTY)
2388  {
2389  Col [next_col].shared3.prev = prev_col ;
2390  }
2391 
2392  /* === Scan the column ========================================== */
2393 
2394  cp = &A [Col [col].start] ;
2395  cp_end = cp + Col [col].length ;
2396  while (cp < cp_end)
2397  {
2398  /* get a row */
2399  row = *cp++ ;
2400  row_mark = Row [row].shared2.mark ;
2401  /* skip if dead */
2402  if (ROW_IS_MARKED_DEAD (row_mark))
2403  {
2404  continue ;
2405  }
2406  ASSERT (row != pivot_row) ;
2407  set_difference = row_mark - tag_mark ;
2408  /* check if the row has been seen yet */
2409  if (set_difference < 0)
2410  {
2411  ASSERT (Row [row].shared1.degree <= max_deg) ;
2412  set_difference = Row [row].shared1.degree ;
2413  }
2414  /* subtract column thickness from this row's set difference */
2415  set_difference -= col_thickness ;
2416  ASSERT (set_difference >= 0) ;
2417  /* absorb this row if the set difference becomes zero */
2418  if (set_difference == 0)
2419  {
2420  DEBUG3 (("aggressive absorption. Row: %d\n", row)) ;
2421  KILL_ROW (row) ;
2422  }
2423  else
2424  {
2425  /* save the new mark */
2426  Row [row].shared2.mark = set_difference + tag_mark ;
2427  }
2428  }
2429  }
2430 
2431 #ifndef NDEBUG
2432  debug_deg_lists (n_row, n_col, Row, Col, head,
2433  min_score, n_col2-k-pivot_row_degree, max_deg) ;
2434 #endif /* NDEBUG */
2435 
2436  /* === Add up set differences for each column ======================= */
2437 
2438  DEBUG3 (("** Adding set differences phase. **\n")) ;
2439 
2440  /* for each column in pivot row */
2441  rp = &A [pivot_row_start] ;
2442  rp_end = rp + pivot_row_length ;
2443  while (rp < rp_end)
2444  {
2445  /* get a column */
2446  col = *rp++ ;
2447  ASSERT (COL_IS_ALIVE (col) && col != pivot_col) ;
2448  hash = 0 ;
2449  cur_score = 0 ;
2450  cp = &A [Col [col].start] ;
2451  /* compact the column */
2452  new_cp = cp ;
2453  cp_end = cp + Col [col].length ;
2454 
2455  DEBUG4 (("Adding set diffs for Col: %d.\n", col)) ;
2456 
2457  while (cp < cp_end)
2458  {
2459  /* get a row */
2460  row = *cp++ ;
2461  ASSERT(row >= 0 && row < n_row) ;
2462  row_mark = Row [row].shared2.mark ;
2463  /* skip if dead */
2464  if (ROW_IS_MARKED_DEAD (row_mark))
2465  {
2466  continue ;
2467  }
2468  ASSERT (row_mark > tag_mark) ;
2469  /* compact the column */
2470  *new_cp++ = row ;
2471  /* compute hash function */
2472  hash += row ;
2473  /* add set difference */
2474  cur_score += row_mark - tag_mark ;
2475  /* integer overflow... */
2476  cur_score = MIN (cur_score, n_col) ;
2477  }
2478 
2479  /* recompute the column's length */
2480  Col [col].length = (int) (new_cp - &A [Col [col].start]) ;
2481 
2482  /* === Further mass elimination ================================= */
2483 
2484  if (Col [col].length == 0)
2485  {
2486  DEBUG4 (("further mass elimination. Col: %d\n", col)) ;
2487  /* nothing left but the pivot row in this column */
2488  KILL_PRINCIPAL_COL (col) ;
2489  pivot_row_degree -= Col [col].shared1.thickness ;
2490  ASSERT (pivot_row_degree >= 0) ;
2491  /* order it */
2492  Col [col].shared2.order = k ;
2493  /* increment order count by column thickness */
2494  k += Col [col].shared1.thickness ;
2495  }
2496  else
2497  {
2498  /* === Prepare for supercolumn detection ==================== */
2499 
2500  DEBUG4 (("Preparing supercol detection for Col: %d.\n", col)) ;
2501 
2502  /* save score so far */
2503  Col [col].shared2.score = cur_score ;
2504 
2505  /* add column to hash table, for supercolumn detection */
2506  hash %= n_col + 1 ;
2507 
2508  DEBUG4 ((" Hash = %d, n_col = %d.\n", hash, n_col)) ;
2509  ASSERT (hash <= n_col) ;
2510 
2511  head_column = head [hash] ;
2512  if (head_column > EMPTY)
2513  {
2514  /* degree list "hash" is non-empty, use prev (shared3) of */
2515  /* first column in degree list as head of hash bucket */
2516  first_col = Col [head_column].shared3.headhash ;
2517  Col [head_column].shared3.headhash = col ;
2518  }
2519  else
2520  {
2521  /* degree list "hash" is empty, use head as hash bucket */
2522  first_col = - (head_column + 2) ;
2523  head [hash] = - (col + 2) ;
2524  }
2525  Col [col].shared4.hash_next = first_col ;
2526 
2527  /* save hash function in Col [col].shared3.hash */
2528  Col [col].shared3.hash = (int) hash ;
2529  ASSERT (COL_IS_ALIVE (col)) ;
2530  }
2531  }
2532 
2533  /* The approximate external column degree is now computed. */
2534 
2535  /* === Supercolumn detection ======================================== */
2536 
2537  DEBUG3 (("** Supercolumn detection phase. **\n")) ;
2538 
2540 
2541 #ifndef NDEBUG
2542  n_col, Row,
2543 #endif /* NDEBUG */
2544 
2545  Col, A, head, pivot_row_start, pivot_row_length) ;
2546 
2547  /* === Kill the pivotal column ====================================== */
2548 
2549  KILL_PRINCIPAL_COL (pivot_col) ;
2550 
2551  /* === Clear mark =================================================== */
2552 
2553  tag_mark += (max_deg + 1) ;
2554  if (tag_mark >= max_mark)
2555  {
2556  DEBUG2 (("clearing tag_mark\n")) ;
2557  tag_mark = clear_mark (n_row, Row) ;
2558  }
2559 
2560 #ifndef NDEBUG
2561  DEBUG3 (("check3\n")) ;
2562  debug_mark (n_row, Row, tag_mark, max_mark) ;
2563 #endif /* NDEBUG */
2564 
2565  /* === Finalize the new pivot row, and column scores ================ */
2566 
2567  DEBUG3 (("** Finalize scores phase. **\n")) ;
2568 
2569  /* for each column in pivot row */
2570  rp = &A [pivot_row_start] ;
2571  /* compact the pivot row */
2572  new_rp = rp ;
2573  rp_end = rp + pivot_row_length ;
2574  while (rp < rp_end)
2575  {
2576  col = *rp++ ;
2577  /* skip dead columns */
2578  if (COL_IS_DEAD (col))
2579  {
2580  continue ;
2581  }
2582  *new_rp++ = col ;
2583  /* add new pivot row to column */
2584  A [Col [col].start + (Col [col].length++)] = pivot_row ;
2585 
2586  /* retrieve score so far and add on pivot row's degree. */
2587  /* (we wait until here for this in case the pivot */
2588  /* row's degree was reduced due to mass elimination). */
2589  cur_score = Col [col].shared2.score + pivot_row_degree ;
2590 
2591  /* calculate the max possible score as the number of */
2592  /* external columns minus the 'k' value minus the */
2593  /* columns thickness */
2594  max_score = n_col - k - Col [col].shared1.thickness ;
2595 
2596  /* make the score the external degree of the union-of-rows */
2597  cur_score -= Col [col].shared1.thickness ;
2598 
2599  /* make sure score is less or equal than the max score */
2600  cur_score = MIN (cur_score, max_score) ;
2601  ASSERT (cur_score >= 0) ;
2602 
2603  /* store updated score */
2604  Col [col].shared2.score = cur_score ;
2605 
2606  /* === Place column back in degree list ========================= */
2607 
2608  ASSERT (min_score >= 0) ;
2609  ASSERT (min_score <= n_col) ;
2610  ASSERT (cur_score >= 0) ;
2611  ASSERT (cur_score <= n_col) ;
2612  ASSERT (head [cur_score] >= EMPTY) ;
2613  next_col = head [cur_score] ;
2614  Col [col].shared4.degree_next = next_col ;
2615  Col [col].shared3.prev = EMPTY ;
2616  if (next_col != EMPTY)
2617  {
2618  Col [next_col].shared3.prev = col ;
2619  }
2620  head [cur_score] = col ;
2621 
2622  /* see if this score is less than current min */
2623  min_score = MIN (min_score, cur_score) ;
2624 
2625  }
2626 
2627 #ifndef NDEBUG
2628  debug_deg_lists (n_row, n_col, Row, Col, head,
2629  min_score, n_col2-k, max_deg) ;
2630 #endif /* NDEBUG */
2631 
2632  /* === Resurrect the new pivot row ================================== */
2633 
2634  if (pivot_row_degree > 0)
2635  {
2636  /* update pivot row length to reflect any cols that were killed */
2637  /* during super-col detection and mass elimination */
2638  Row [pivot_row].start = pivot_row_start ;
2639  Row [pivot_row].length = (int) (new_rp - &A[pivot_row_start]) ;
2640  Row [pivot_row].shared1.degree = pivot_row_degree ;
2641  Row [pivot_row].shared2.mark = 0 ;
2642  /* pivot row is no longer dead */
2643  }
2644  }
2645 
2646  /* === All principal columns have now been ordered ====================== */
2647 
2648  return (ngarbage) ;
2649 }
static integer clear_mark(integer n_row, mbdyn_Colamd_Row Row[])
Definition: colamd.c:3064
#define COL_IS_ALIVE(c)
Definition: colamd.c:783
union mbdyn_Colamd_Col::@1 shared2
#define KILL_ROW(r)
Definition: colamd.c:785
#define DEBUG2(params)
Definition: colamd.c:973
#define NDEBUG
Definition: colamd.c:692
integer start
Definition: colamd.h:194
#define DEBUG3(params)
Definition: colamd.c:974
#define ROW_IS_DEAD(r)
Definition: colamd.c:779
integer score
Definition: colamd.h:173
#define MIN(a, b)
Definition: colamd.c:750
union mbdyn_Colamd_Col::@0 shared1
integer thickness
Definition: colamd.h:166
static void detect_super_cols(mbdyn_Colamd_Col Col[], integer A[], integer head[], integer row_start, integer row_length)
Definition: colamd.c:2771
#define COL_IS_DEAD(c)
Definition: colamd.c:782
#define ASSERT(expression)
Definition: colamd.c:977
integer prev
Definition: colamd.h:181
union mbdyn_Colamd_Col::@3 shared4
integer start
Definition: colamd.h:161
#define KILL_PRINCIPAL_COL(c)
Definition: colamd.c:786
integer order
Definition: colamd.h:174
integer degree_next
Definition: colamd.h:186
#define MAX(a, b)
Definition: colamd.c:749
#define EMPTY
Definition: colamd.c:768
union mbdyn_Colamd_Col::@2 shared3
static integer garbage_collection(integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer *pfree)
Definition: colamd.c:2928
#define ROW_IS_ALIVE(r)
Definition: colamd.c:781
long int integer
Definition: colamd.c:51
#define ROW_IS_MARKED_DEAD(row_mark)
Definition: colamd.c:780
#define DEBUG1(params)
Definition: colamd.c:972
#define DEBUG4(params)
Definition: colamd.c:975

Here is the call graph for this function:

static integer garbage_collection ( integer  n_row,
integer  n_col,
mbdyn_Colamd_Row  Row[],
mbdyn_Colamd_Col  Col[],
integer  A[],
integer pfree 
)
static

Definition at line 2928 of file colamd.c.

References ASSERT, c, COL_IS_ALIVE, DEBUG2, DEBUG3, KILL_ROW, ONES_COMPLEMENT, and ROW_IS_ALIVE.

Referenced by find_ordering().

2938 {
2939  /* === Local variables ================================================== */
2940 
2941  integer *psrc ; /* source pointer */
2942  integer *pdest ; /* destination pointer */
2943  integer j ; /* counter */
2944  integer r ; /* a row index */
2945  integer c ; /* a column index */
2946  integer length ; /* length of a row or column */
2947 
2948 #ifndef NDEBUG
2949  integer debug_rows ;
2950  DEBUG2 (("Defrag..\n")) ;
2951  for (psrc = &A[0] ; psrc < pfree ; psrc++) ASSERT (*psrc >= 0) ;
2952  debug_rows = 0 ;
2953 #endif /* NDEBUG */
2954 
2955  /* === Defragment the columns =========================================== */
2956 
2957  pdest = &A[0] ;
2958  for (c = 0 ; c < n_col ; c++)
2959  {
2960  if (COL_IS_ALIVE (c))
2961  {
2962  psrc = &A [Col [c].start] ;
2963 
2964  /* move and compact the column */
2965  ASSERT (pdest <= psrc) ;
2966  Col [c].start = (int) (pdest - &A [0]) ;
2967  length = Col [c].length ;
2968  for (j = 0 ; j < length ; j++)
2969  {
2970  r = *psrc++ ;
2971  if (ROW_IS_ALIVE (r))
2972  {
2973  *pdest++ = r ;
2974  }
2975  }
2976  Col [c].length = (int) (pdest - &A [Col [c].start]) ;
2977  }
2978  }
2979 
2980  /* === Prepare to defragment the rows =================================== */
2981 
2982  for (r = 0 ; r < n_row ; r++)
2983  {
2984  if (ROW_IS_ALIVE (r))
2985  {
2986  if (Row [r].length == 0)
2987  {
2988  /* this row is of zero length. cannot compact it, so kill it */
2989  DEBUG3 (("Defrag row kill\n")) ;
2990  KILL_ROW (r) ;
2991  }
2992  else
2993  {
2994  /* save first column index in Row [r].shared2.first_column */
2995  psrc = &A [Row [r].start] ;
2996  Row [r].shared2.first_column = *psrc ;
2997  ASSERT (ROW_IS_ALIVE (r)) ;
2998  /* flag the start of the row with the one's complement of row */
2999  *psrc = ONES_COMPLEMENT (r) ;
3000 
3001 #ifndef NDEBUG
3002  debug_rows++ ;
3003 #endif /* NDEBUG */
3004 
3005  }
3006  }
3007  }
3008 
3009  /* === Defragment the rows ============================================== */
3010 
3011  psrc = pdest ;
3012  while (psrc < pfree)
3013  {
3014  /* find a negative number ... the start of a row */
3015  if (*psrc++ < 0)
3016  {
3017  psrc-- ;
3018  /* get the row index */
3019  r = ONES_COMPLEMENT (*psrc) ;
3020  ASSERT (r >= 0 && r < n_row) ;
3021  /* restore first column index */
3022  *psrc = Row [r].shared2.first_column ;
3023  ASSERT (ROW_IS_ALIVE (r)) ;
3024 
3025  /* move and compact the row */
3026  ASSERT (pdest <= psrc) ;
3027  Row [r].start = (int) (pdest - &A [0]) ;
3028  length = Row [r].length ;
3029  for (j = 0 ; j < length ; j++)
3030  {
3031  c = *psrc++ ;
3032  if (COL_IS_ALIVE (c))
3033  {
3034  *pdest++ = c ;
3035  }
3036  }
3037  Row [r].length = (int) (pdest - &A [Row [r].start]) ;
3038 
3039 #ifndef NDEBUG
3040  debug_rows-- ;
3041 #endif /* NDEBUG */
3042 
3043  }
3044  }
3045  /* ensure we found all the rows */
3046  ASSERT (debug_rows == 0) ;
3047 
3048  /* === Return the new value of pfree ==================================== */
3049 
3050  return ((int) (pdest - &A [0])) ;
3051 }
integer first_column
Definition: colamd.h:204
#define COL_IS_ALIVE(c)
Definition: colamd.c:783
#define KILL_ROW(r)
Definition: colamd.c:785
#define DEBUG2(params)
Definition: colamd.c:973
integer start
Definition: colamd.h:194
#define DEBUG3(params)
Definition: colamd.c:974
union mbdyn_Colamd_Row::@5 shared2
#define ASSERT(expression)
Definition: colamd.c:977
integer length
Definition: colamd.h:195
static std::stack< cleanup * > c
Definition: cleanup.cc:59
integer start
Definition: colamd.h:161
#define ONES_COMPLEMENT(r)
Definition: colamd.c:752
#define ROW_IS_ALIVE(r)
Definition: colamd.c:781
long int integer
Definition: colamd.c:51
static integer init_rows_cols ( integer  n_row,
integer  n_col,
mbdyn_Colamd_Row  Row[],
mbdyn_Colamd_Col  Col[],
integer  A[],
integer  p[],
integer  stats[20] 
)
static

Definition at line 1613 of file colamd.c.

References ASSERT, COLAMD_ERROR_col_length_negative, COLAMD_ERROR_row_index_out_of_bounds, COLAMD_INFO1, COLAMD_INFO2, COLAMD_INFO3, COLAMD_OK_BUT_JUMBLED, COLAMD_STATUS, DEBUG0, DEBUG1, EMPTY, FALSE, and TRUE.

Referenced by mbdyn_colamd().

1624 {
1625  /* === Local variables ================================================== */
1626 
1627  integer col ; /* a column index */
1628  integer row ; /* a row index */
1629  integer *cp ; /* a column pointer */
1630  integer *cp_end ; /* a pointer to the end of a column */
1631  integer *rp ; /* a row pointer */
1632  integer *rp_end ; /* a pointer to the end of a row */
1633  integer last_row ; /* previous row */
1634 
1635  /* === Initialize columns, and check column pointers ==================== */
1636 
1637  for (col = 0 ; col < n_col ; col++)
1638  {
1639  Col [col].start = p [col] ;
1640  Col [col].length = p [col+1] - p [col] ;
1641 
1642  if (Col [col].length < 0)
1643  {
1644  /* column pointers must be non-decreasing */
1646  stats [COLAMD_INFO1] = col ;
1647  stats [COLAMD_INFO2] = Col [col].length ;
1648  DEBUG0 (("colamd: col %d length %d < 0\n", col, Col [col].length)) ;
1649  return (FALSE) ;
1650  }
1651 
1652  Col [col].shared1.thickness = 1 ;
1653  Col [col].shared2.score = 0 ;
1654  Col [col].shared3.prev = EMPTY ;
1655  Col [col].shared4.degree_next = EMPTY ;
1656  }
1657 
1658  /* p [0..n_col] no longer needed, used as "head" in subsequent routines */
1659 
1660  /* === Scan columns, compute row degrees, and check row indices ========= */
1661 
1662  stats [COLAMD_INFO3] = 0 ; /* number of duplicate or unsorted row indices*/
1663 
1664  for (row = 0 ; row < n_row ; row++)
1665  {
1666  Row [row].length = 0 ;
1667  Row [row].shared2.mark = -1 ;
1668  }
1669 
1670  for (col = 0 ; col < n_col ; col++)
1671  {
1672  last_row = -1 ;
1673 
1674  cp = &A [p [col]] ;
1675  cp_end = &A [p [col+1]] ;
1676 
1677  while (cp < cp_end)
1678  {
1679  row = *cp++ ;
1680 
1681  /* make sure row indices within range */
1682  if (row < 0 || row >= n_row)
1683  {
1685  stats [COLAMD_INFO1] = col ;
1686  stats [COLAMD_INFO2] = row ;
1687  stats [COLAMD_INFO3] = n_row ;
1688  DEBUG0 (("colamd: row %d col %d out of bounds\n", row, col)) ;
1689  return (FALSE) ;
1690  }
1691 
1692  if (row <= last_row || Row [row].shared2.mark == col)
1693  {
1694  /* row index are unsorted or repeated (or both), thus col */
1695  /* is jumbled. This is a notice, not an error condition. */
1697  stats [COLAMD_INFO1] = col ;
1698  stats [COLAMD_INFO2] = row ;
1699  (stats [COLAMD_INFO3]) ++ ;
1700  DEBUG1 (("colamd: row %d col %d unsorted/duplicate\n",row,col));
1701  }
1702 
1703  if (Row [row].shared2.mark != col)
1704  {
1705  Row [row].length++ ;
1706  }
1707  else
1708  {
1709  /* this is a repeated entry in the column, */
1710  /* it will be removed */
1711  Col [col].length-- ;
1712  }
1713 
1714  /* mark the row as having been seen in this column */
1715  Row [row].shared2.mark = col ;
1716 
1717  last_row = row ;
1718  }
1719  }
1720 
1721  /* === Compute row pointers ============================================= */
1722 
1723  /* row form of the matrix starts directly after the column */
1724  /* form of matrix in A */
1725  Row [0].start = p [n_col] ;
1726  Row [0].shared1.p = Row [0].start ;
1727  Row [0].shared2.mark = -1 ;
1728  for (row = 1 ; row < n_row ; row++)
1729  {
1730  Row [row].start = Row [row-1].start + Row [row-1].length ;
1731  Row [row].shared1.p = Row [row].start ;
1732  Row [row].shared2.mark = -1 ;
1733  }
1734 
1735  /* === Create row form ================================================== */
1736 
1737  if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED)
1738  {
1739  /* if cols jumbled, watch for repeated row indices */
1740  for (col = 0 ; col < n_col ; col++)
1741  {
1742  cp = &A [p [col]] ;
1743  cp_end = &A [p [col+1]] ;
1744  while (cp < cp_end)
1745  {
1746  row = *cp++ ;
1747  if (Row [row].shared2.mark != col)
1748  {
1749  A [(Row [row].shared1.p)++] = col ;
1750  Row [row].shared2.mark = col ;
1751  }
1752  }
1753  }
1754  }
1755  else
1756  {
1757  /* if cols not jumbled, we don't need the mark (this is faster) */
1758  for (col = 0 ; col < n_col ; col++)
1759  {
1760  cp = &A [p [col]] ;
1761  cp_end = &A [p [col+1]] ;
1762  while (cp < cp_end)
1763  {
1764  A [(Row [*cp++].shared1.p)++] = col ;
1765  }
1766  }
1767  }
1768 
1769  /* === Clear the row marks and set row degrees ========================== */
1770 
1771  for (row = 0 ; row < n_row ; row++)
1772  {
1773  Row [row].shared2.mark = 0 ;
1774  Row [row].shared1.degree = Row [row].length ;
1775  }
1776 
1777  /* === See if we need to re-create columns ============================== */
1778 
1779  if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED)
1780  {
1781  DEBUG0 (("colamd: reconstructing column form, matrix jumbled\n")) ;
1782 
1783 #ifndef NDEBUG
1784  /* make sure column lengths are correct */
1785  for (col = 0 ; col < n_col ; col++)
1786  {
1787  p [col] = Col [col].length ;
1788  }
1789  for (row = 0 ; row < n_row ; row++)
1790  {
1791  rp = &A [Row [row].start] ;
1792  rp_end = rp + Row [row].length ;
1793  while (rp < rp_end)
1794  {
1795  p [*rp++]-- ;
1796  }
1797  }
1798  for (col = 0 ; col < n_col ; col++)
1799  {
1800  ASSERT (p [col] == 0) ;
1801  }
1802  /* now p is all zero (different than when debugging is turned off) */
1803 #endif /* NDEBUG */
1804 
1805  /* === Compute col pointers ========================================= */
1806 
1807  /* col form of the matrix starts at A [0]. */
1808  /* Note, we may have a gap between the col form and the row */
1809  /* form if there were duplicate entries, if so, it will be */
1810  /* removed upon the first garbage collection */
1811  Col [0].start = 0 ;
1812  p [0] = Col [0].start ;
1813  for (col = 1 ; col < n_col ; col++)
1814  {
1815  /* note that the lengths here are for pruned columns, i.e. */
1816  /* no duplicate row indices will exist for these columns */
1817  Col [col].start = Col [col-1].start + Col [col-1].length ;
1818  p [col] = Col [col].start ;
1819  }
1820 
1821  /* === Re-create col form =========================================== */
1822 
1823  for (row = 0 ; row < n_row ; row++)
1824  {
1825  rp = &A [Row [row].start] ;
1826  rp_end = rp + Row [row].length ;
1827  while (rp < rp_end)
1828  {
1829  A [(p [*rp++])++] = row ;
1830  }
1831  }
1832  }
1833 
1834  /* === Done. Matrix is not (or no longer) jumbled ====================== */
1835 
1836  return (TRUE) ;
1837 }
integer p
Definition: colamd.h:199
#define COLAMD_INFO2
Definition: colamd.h:133
#define COLAMD_ERROR_col_length_negative
Definition: colamd.h:146
union mbdyn_Colamd_Col::@1 shared2
#define COLAMD_INFO3
Definition: colamd.h:134
integer degree
Definition: colamd.h:198
integer start
Definition: colamd.h:194
#define TRUE
Definition: colamd.c:759
integer score
Definition: colamd.h:173
union mbdyn_Colamd_Row::@4 shared1
union mbdyn_Colamd_Col::@0 shared1
integer thickness
Definition: colamd.h:166
union mbdyn_Colamd_Row::@5 shared2
#define COLAMD_OK_BUT_JUMBLED
Definition: colamd.h:138
#define ASSERT(expression)
Definition: colamd.c:977
integer mark
Definition: colamd.h:203
#define COLAMD_INFO1
Definition: colamd.h:132
integer length
Definition: colamd.h:195
integer prev
Definition: colamd.h:181
union mbdyn_Colamd_Col::@3 shared4
integer length
Definition: colamd.h:163
integer start
Definition: colamd.h:161
#define COLAMD_ERROR_row_index_out_of_bounds
Definition: colamd.h:147
integer degree_next
Definition: colamd.h:186
#define FALSE
Definition: colamd.c:763
#define EMPTY
Definition: colamd.c:768
union mbdyn_Colamd_Col::@2 shared3
#define DEBUG0(params)
Definition: colamd.c:971
long int integer
Definition: colamd.c:51
#define COLAMD_STATUS
Definition: colamd.h:129
#define DEBUG1(params)
Definition: colamd.c:972
static void init_scoring ( integer  n_row,
integer  n_col,
mbdyn_Colamd_Row  Row[],
mbdyn_Colamd_Col  Col[],
integer  A[],
integer  head[],
double  knobs[20],
integer p_n_row2,
integer p_n_col2,
integer p_max_deg 
)
static

Definition at line 1850 of file colamd.c.

References ASSERT, c, COL_IS_ALIVE, COL_IS_DEAD, COLAMD_DENSE_COL, COLAMD_DENSE_ROW, DEBUG1, DEBUG2, DEBUG4, mbdyn_Colamd_Row::degree, mbdyn_Colamd_Col::degree_next, EMPTY, KILL_PRINCIPAL_COL, KILL_ROW, mbdyn_Colamd_Col::length, MAX, MIN, mbdyn_Colamd_Col::order, mbdyn_Colamd_Col::prev, ROW_IS_DEAD, mbdyn_Colamd_Col::score, mbdyn_Colamd_Row::shared1, mbdyn_Colamd_Col::shared2, mbdyn_Colamd_Col::shared3, mbdyn_Colamd_Col::shared4, and mbdyn_Colamd_Col::start.

Referenced by mbdyn_colamd().

1864 {
1865  /* === Local variables ================================================== */
1866 
1867  integer c ; /* a column index */
1868  integer r, row ; /* a row index */
1869  integer *cp ; /* a column pointer */
1870  integer deg ; /* degree of a row or column */
1871  integer *cp_end ; /* a pointer to the end of a column */
1872  integer *new_cp ; /* new column pointer */
1873  integer col_length ; /* length of pruned column */
1874  integer score ; /* current column score */
1875  integer n_col2 ; /* number of non-dense, non-empty columns */
1876  integer n_row2 ; /* number of non-dense, non-empty rows */
1877  integer dense_row_count ; /* remove rows with more entries than this */
1878  integer dense_col_count ; /* remove cols with more entries than this */
1879  integer min_score ; /* smallest column score */
1880  integer max_deg ; /* maximum row degree */
1881  integer next_col ; /* Used to add to degree list.*/
1882 
1883 #ifndef NDEBUG
1884  integer debug_count ; /* debug only. */
1885 #endif /* NDEBUG */
1886 
1887  /* === Extract knobs ==================================================== */
1888 
1889  dense_row_count = MAX (0, MIN (knobs [COLAMD_DENSE_ROW] * n_col, n_col)) ;
1890  dense_col_count = MAX (0, MIN (knobs [COLAMD_DENSE_COL] * n_row, n_row)) ;
1891  DEBUG1 (("colamd: densecount: %d %d\n", dense_row_count, dense_col_count)) ;
1892  max_deg = 0 ;
1893  n_col2 = n_col ;
1894  n_row2 = n_row ;
1895 
1896  /* === Kill empty columns =============================================== */
1897 
1898  /* Put the empty columns at the end in their natural order, so that LU */
1899  /* factorization can proceed as far as possible. */
1900  for (c = n_col-1 ; c >= 0 ; c--)
1901  {
1902  deg = Col [c].length ;
1903  if (deg == 0)
1904  {
1905  /* this is a empty column, kill and order it last */
1906  Col [c].shared2.order = --n_col2 ;
1907  KILL_PRINCIPAL_COL (c) ;
1908  }
1909  }
1910  DEBUG1 (("colamd: null columns killed: %d\n", n_col - n_col2)) ;
1911 
1912  /* === Kill dense columns =============================================== */
1913 
1914  /* Put the dense columns at the end, in their natural order */
1915  for (c = n_col-1 ; c >= 0 ; c--)
1916  {
1917  /* skip any dead columns */
1918  if (COL_IS_DEAD (c))
1919  {
1920  continue ;
1921  }
1922  deg = Col [c].length ;
1923  if (deg > dense_col_count)
1924  {
1925  /* this is a dense column, kill and order it last */
1926  Col [c].shared2.order = --n_col2 ;
1927  /* decrement the row degrees */
1928  cp = &A [Col [c].start] ;
1929  cp_end = cp + Col [c].length ;
1930  while (cp < cp_end)
1931  {
1932  Row [*cp++].shared1.degree-- ;
1933  }
1934  KILL_PRINCIPAL_COL (c) ;
1935  }
1936  }
1937  DEBUG1 (("colamd: Dense and null columns killed: %d\n", n_col - n_col2)) ;
1938 
1939  /* === Kill dense and empty rows ======================================== */
1940 
1941  for (r = 0 ; r < n_row ; r++)
1942  {
1943  deg = Row [r].shared1.degree ;
1944  ASSERT (deg >= 0 && deg <= n_col) ;
1945  if (deg > dense_row_count || deg == 0)
1946  {
1947  /* kill a dense or empty row */
1948  KILL_ROW (r) ;
1949  --n_row2 ;
1950  }
1951  else
1952  {
1953  /* keep track of max degree of remaining rows */
1954  max_deg = MAX (max_deg, deg) ;
1955  }
1956  }
1957  DEBUG1 (("colamd: Dense and null rows killed: %d\n", n_row - n_row2)) ;
1958 
1959  /* === Compute initial column scores ==================================== */
1960 
1961  /* At this point the row degrees are accurate. They reflect the number */
1962  /* of "live" (non-dense) columns in each row. No empty rows exist. */
1963  /* Some "live" columns may contain only dead rows, however. These are */
1964  /* pruned in the code below. */
1965 
1966  /* now find the initial matlab score for each column */
1967  for (c = n_col-1 ; c >= 0 ; c--)
1968  {
1969  /* skip dead column */
1970  if (COL_IS_DEAD (c))
1971  {
1972  continue ;
1973  }
1974  score = 0 ;
1975  cp = &A [Col [c].start] ;
1976  new_cp = cp ;
1977  cp_end = cp + Col [c].length ;
1978  while (cp < cp_end)
1979  {
1980  /* get a row */
1981  row = *cp++ ;
1982  /* skip if dead */
1983  if (ROW_IS_DEAD (row))
1984  {
1985  continue ;
1986  }
1987  /* compact the column */
1988  *new_cp++ = row ;
1989  /* add row's external degree */
1990  score += Row [row].shared1.degree - 1 ;
1991  /* guard against integer overflow */
1992  score = MIN (score, n_col) ;
1993  }
1994  /* determine pruned column length */
1995  col_length = (int) (new_cp - &A [Col [c].start]) ;
1996  if (col_length == 0)
1997  {
1998  /* a newly-made null column (all rows in this col are "dense" */
1999  /* and have already been killed) */
2000  DEBUG2 (("Newly null killed: %d\n", c)) ;
2001  Col [c].shared2.order = --n_col2 ;
2002  KILL_PRINCIPAL_COL (c) ;
2003  }
2004  else
2005  {
2006  /* set column length and set score */
2007  ASSERT (score >= 0) ;
2008  ASSERT (score <= n_col) ;
2009  Col [c].length = col_length ;
2010  Col [c].shared2.score = score ;
2011  }
2012  }
2013  DEBUG1 (("colamd: Dense, null, and newly-null columns killed: %d\n",
2014  n_col-n_col2)) ;
2015 
2016  /* At this point, all empty rows and columns are dead. All live columns */
2017  /* are "clean" (containing no dead rows) and simplicial (no supercolumns */
2018  /* yet). Rows may contain dead columns, but all live rows contain at */
2019  /* least one live column. */
2020 
2021 #ifndef NDEBUG
2022  debug_structures (n_row, n_col, Row, Col, A, n_col2) ;
2023 #endif /* NDEBUG */
2024 
2025  /* === Initialize degree lists ========================================== */
2026 
2027 #ifndef NDEBUG
2028  debug_count = 0 ;
2029 #endif /* NDEBUG */
2030 
2031  /* clear the hash buckets */
2032  for (c = 0 ; c <= n_col ; c++)
2033  {
2034  head [c] = EMPTY ;
2035  }
2036  min_score = n_col ;
2037  /* place in reverse order, so low column indices are at the front */
2038  /* of the lists. This is to encourage natural tie-breaking */
2039  for (c = n_col-1 ; c >= 0 ; c--)
2040  {
2041  /* only add principal columns to degree lists */
2042  if (COL_IS_ALIVE (c))
2043  {
2044  DEBUG4 (("place %d score %d minscore %d ncol %d\n",
2045  c, Col [c].shared2.score, min_score, n_col)) ;
2046 
2047  /* === Add columns score to DList =============================== */
2048 
2049  score = Col [c].shared2.score ;
2050 
2051  ASSERT (min_score >= 0) ;
2052  ASSERT (min_score <= n_col) ;
2053  ASSERT (score >= 0) ;
2054  ASSERT (score <= n_col) ;
2055  ASSERT (head [score] >= EMPTY) ;
2056 
2057  /* now add this column to dList at proper score location */
2058  next_col = head [score] ;
2059  Col [c].shared3.prev = EMPTY ;
2060  Col [c].shared4.degree_next = next_col ;
2061 
2062  /* if there already was a column with the same score, set its */
2063  /* previous pointer to this new column */
2064  if (next_col != EMPTY)
2065  {
2066  Col [next_col].shared3.prev = c ;
2067  }
2068  head [score] = c ;
2069 
2070  /* see if this score is less than current min */
2071  min_score = MIN (min_score, score) ;
2072 
2073 #ifndef NDEBUG
2074  debug_count++ ;
2075 #endif /* NDEBUG */
2076 
2077  }
2078  }
2079 
2080 #ifndef NDEBUG
2081  DEBUG1 (("colamd: Live cols %d out of %d, non-princ: %d\n",
2082  debug_count, n_col, n_col-debug_count)) ;
2083  ASSERT (debug_count == n_col2) ;
2084  debug_deg_lists (n_row, n_col, Row, Col, head, min_score, n_col2, max_deg) ;
2085 #endif /* NDEBUG */
2086 
2087  /* === Return number of remaining columns, and max row degree =========== */
2088 
2089  *p_n_col2 = n_col2 ;
2090  *p_n_row2 = n_row2 ;
2091  *p_max_deg = max_deg ;
2092 }
#define COL_IS_ALIVE(c)
Definition: colamd.c:783
union mbdyn_Colamd_Col::@1 shared2
#define KILL_ROW(r)
Definition: colamd.c:785
#define DEBUG2(params)
Definition: colamd.c:973
#define COLAMD_DENSE_COL
Definition: colamd.h:123
integer degree
Definition: colamd.h:198
#define ROW_IS_DEAD(r)
Definition: colamd.c:779
#define MIN(a, b)
Definition: colamd.c:750
union mbdyn_Colamd_Row::@4 shared1
#define COL_IS_DEAD(c)
Definition: colamd.c:782
#define ASSERT(expression)
Definition: colamd.c:977
#define COLAMD_DENSE_ROW
Definition: colamd.h:120
static std::stack< cleanup * > c
Definition: cleanup.cc:59
integer length
Definition: colamd.h:163
integer start
Definition: colamd.h:161
#define KILL_PRINCIPAL_COL(c)
Definition: colamd.c:786
integer order
Definition: colamd.h:174
#define MAX(a, b)
Definition: colamd.c:749
#define EMPTY
Definition: colamd.c:768
long int integer
Definition: colamd.c:51
#define DEBUG1(params)
Definition: colamd.c:972
#define DEBUG4(params)
Definition: colamd.c:975
integer mbdyn_colamd ( integer  n_row,
integer  n_col,
integer  Alen,
integer  A[],
integer  p[],
double  knobs[20],
integer  stats[20] 
)

Definition at line 1411 of file colamd.c.

References COLAMD_C, COLAMD_DEFRAG_COUNT, COLAMD_DENSE_COL, COLAMD_DENSE_ROW, COLAMD_ERROR_A_not_present, COLAMD_ERROR_A_too_small, COLAMD_ERROR_ncol_negative, COLAMD_ERROR_nnz_negative, COLAMD_ERROR_nrow_negative, COLAMD_ERROR_p0_nonzero, COLAMD_ERROR_p_not_present, COLAMD_INFO1, COLAMD_INFO2, COLAMD_KNOBS, COLAMD_OK, COLAMD_R, COLAMD_STATS, COLAMD_STATUS, DEBUG0, FALSE, find_ordering(), init_rows_cols(), init_scoring(), mbdyn_colamd_set_defaults(), order_children(), and TRUE.

Referenced by NaiveSparsePermSolutionManager< T >::ComputePermutation(), and mbdyn_symamd().

1422 {
1423  /* === Local variables ================================================== */
1424 
1425  integer i ; /* loop index */
1426  integer nnz ; /* nonzeros in A */
1427  integer Row_size ; /* size of Row [], in integers */
1428  integer Col_size ; /* size of Col [], in integers */
1429  integer need ; /* minimum required length of A */
1430  mbdyn_Colamd_Row *Row ; /* pointer into A of Row [0..n_row] array */
1431  mbdyn_Colamd_Col *Col ; /* pointer into A of Col [0..n_col] array */
1432  integer n_col2 ; /* number of non-dense, non-empty columns */
1433  integer n_row2 ; /* number of non-dense, non-empty rows */
1434  integer ngarbage ; /* number of garbage collections performed */
1435  integer max_deg ; /* maximum row degree */
1436  double default_knobs [COLAMD_KNOBS] ; /* default knobs array */
1437 
1438 #ifndef NDEBUG
1439  colamd_get_debug ("colamd") ;
1440 #endif /* NDEBUG */
1441 
1442  /* === Check the input arguments ======================================== */
1443 
1444  if (!stats)
1445  {
1446  DEBUG0 (("colamd: stats not present\n")) ;
1447  return (FALSE) ;
1448  }
1449  for (i = 0 ; i < COLAMD_STATS ; i++)
1450  {
1451  stats [i] = 0 ;
1452  }
1453  stats [COLAMD_STATUS] = COLAMD_OK ;
1454  stats [COLAMD_INFO1] = -1 ;
1455  stats [COLAMD_INFO2] = -1 ;
1456 
1457  if (!A) /* A is not present */
1458  {
1460  DEBUG0 (("colamd: A not present\n")) ;
1461  return (FALSE) ;
1462  }
1463 
1464  if (!p) /* p is not present */
1465  {
1467  DEBUG0 (("colamd: p not present\n")) ;
1468  return (FALSE) ;
1469  }
1470 
1471  if (n_row < 0) /* n_row must be >= 0 */
1472  {
1474  stats [COLAMD_INFO1] = n_row ;
1475  DEBUG0 (("colamd: nrow negative %d\n", n_row)) ;
1476  return (FALSE) ;
1477  }
1478 
1479  if (n_col < 0) /* n_col must be >= 0 */
1480  {
1482  stats [COLAMD_INFO1] = n_col ;
1483  DEBUG0 (("colamd: ncol negative %d\n", n_col)) ;
1484  return (FALSE) ;
1485  }
1486 
1487  nnz = p [n_col] ;
1488  if (nnz < 0) /* nnz must be >= 0 */
1489  {
1491  stats [COLAMD_INFO1] = nnz ;
1492  DEBUG0 (("colamd: number of entries negative %d\n", nnz)) ;
1493  return (FALSE) ;
1494  }
1495 
1496  if (p [0] != 0)
1497  {
1499  stats [COLAMD_INFO1] = p [0] ;
1500  DEBUG0 (("colamd: p[0] not zero %d\n", p [0])) ;
1501  return (FALSE) ;
1502  }
1503 
1504  /* === If no knobs, set default knobs =================================== */
1505 
1506  if (!knobs)
1507  {
1508  mbdyn_colamd_set_defaults (default_knobs) ;
1509  knobs = default_knobs ;
1510  }
1511 
1512  /* === Allocate the Row and Col arrays from array A ===================== */
1513 
1514  Col_size = COLAMD_C (n_col) ;
1515  Row_size = COLAMD_R (n_row) ;
1516  need = 2*nnz + n_col + Col_size + Row_size ;
1517 
1518  if (need > Alen)
1519  {
1520  /* not enough space in array A to perform the ordering */
1522  stats [COLAMD_INFO1] = need ;
1523  stats [COLAMD_INFO2] = Alen ;
1524  DEBUG0 (("colamd: Need Alen >= %d, given only Alen = %d\n", need,Alen));
1525  return (FALSE) ;
1526  }
1527 
1528  Alen -= Col_size + Row_size ;
1529  Col = (mbdyn_Colamd_Col *) &A [Alen] ;
1530  Row = (mbdyn_Colamd_Row *) &A [Alen + Col_size] ;
1531 
1532  /* === Construct the row and column data structures ===================== */
1533 
1534  if (!init_rows_cols (n_row, n_col, Row, Col, A, p, stats))
1535  {
1536  /* input matrix is invalid */
1537  DEBUG0 (("colamd: Matrix invalid\n")) ;
1538  return (FALSE) ;
1539  }
1540 
1541  /* === Initialize scores, kill dense rows/columns ======================= */
1542 
1543  init_scoring (n_row, n_col, Row, Col, A, p, knobs,
1544  &n_row2, &n_col2, &max_deg) ;
1545 
1546  /* === Order the supercolumns =========================================== */
1547 
1548  ngarbage = find_ordering (n_row, n_col, Alen, Row, Col, A, p,
1549  n_col2, max_deg, 2*nnz) ;
1550 
1551  /* === Order the non-principal columns ================================== */
1552 
1553  order_children (n_col, Col, p) ;
1554 
1555  /* === Return statistics in stats ======================================= */
1556 
1557  stats [COLAMD_DENSE_ROW] = n_row - n_row2 ;
1558  stats [COLAMD_DENSE_COL] = n_col - n_col2 ;
1559  stats [COLAMD_DEFRAG_COUNT] = ngarbage ;
1560  DEBUG0 (("colamd: done.\n")) ;
1561  return (TRUE) ;
1562 }
#define COLAMD_DEFRAG_COUNT
Definition: colamd.h:126
#define COLAMD_R(n_row)
Definition: colamd.h:226
static void order_children(integer n_col, mbdyn_Colamd_Col Col[], integer p[])
Definition: colamd.c:2670
static integer init_rows_cols(integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer p[], integer stats[20])
Definition: colamd.c:1613
static void init_scoring(integer n_row, integer n_col, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer head[], double knobs[20], integer *p_n_row2, integer *p_n_col2, integer *p_max_deg)
Definition: colamd.c:1850
#define COLAMD_INFO2
Definition: colamd.h:133
void mbdyn_colamd_set_defaults(double knobs[20])
Definition: colamd.c:1038
#define COLAMD_STATS
Definition: colamd.h:117
#define COLAMD_DENSE_COL
Definition: colamd.h:123
static integer find_ordering(integer n_row, integer n_col, integer Alen, mbdyn_Colamd_Row Row[], mbdyn_Colamd_Col Col[], integer A[], integer head[], integer n_col2, integer max_deg, integer pfree)
Definition: colamd.c:2106
#define COLAMD_ERROR_p_not_present
Definition: colamd.h:140
#define COLAMD_ERROR_A_too_small
Definition: colamd.h:145
#define COLAMD_ERROR_A_not_present
Definition: colamd.h:139
#define TRUE
Definition: colamd.c:759
#define COLAMD_KNOBS
Definition: colamd.h:114
#define COLAMD_OK
Definition: colamd.h:137
#define COLAMD_DENSE_ROW
Definition: colamd.h:120
#define COLAMD_INFO1
Definition: colamd.h:132
#define COLAMD_C(n_col)
Definition: colamd.h:225
#define COLAMD_ERROR_ncol_negative
Definition: colamd.h:142
#define COLAMD_ERROR_nrow_negative
Definition: colamd.h:141
#define FALSE
Definition: colamd.c:763
#define DEBUG0(params)
Definition: colamd.c:971
long int integer
Definition: colamd.c:51
#define COLAMD_STATUS
Definition: colamd.h:129
#define COLAMD_ERROR_nnz_negative
Definition: colamd.h:143
#define COLAMD_ERROR_p0_nonzero
Definition: colamd.h:144

Here is the call graph for this function:

integer mbdyn_colamd_recommended ( integer  nnz,
integer  n_row,
integer  n_col 
)

Definition at line 1004 of file colamd.c.

References COLAMD_RECOMMENDED.

Referenced by NaiveSparsePermSolutionManager< T >::ComputePermutation(), and mbdyn_symamd().

1011 {
1012  return (COLAMD_RECOMMENDED (nnz, n_row, n_col)) ;
1013 }
#define COLAMD_RECOMMENDED(nnz, n_row, n_col)
Definition: colamd.h:228
void mbdyn_colamd_report ( integer  stats[20])

Definition at line 1570 of file colamd.c.

References print_report().

1573 {
1574  print_report ("colamd", stats) ;
1575 }
static void print_report(char *method, integer stats[20])
Definition: colamd.c:3091

Here is the call graph for this function:

void mbdyn_colamd_set_defaults ( double  knobs[20])

Definition at line 1038 of file colamd.c.

References COLAMD_DENSE_COL, COLAMD_DENSE_ROW, and COLAMD_KNOBS.

Referenced by NaiveSparsePermSolutionManager< T >::ComputePermutation(), mbdyn_colamd(), and mbdyn_symamd().

1043 {
1044  /* === Local variables ================================================== */
1045 
1046  integer i ;
1047 
1048  if (!knobs)
1049  {
1050  return ; /* no knobs to initialize */
1051  }
1052  for (i = 0 ; i < COLAMD_KNOBS ; i++)
1053  {
1054  knobs [i] = 0 ;
1055  }
1056  knobs [COLAMD_DENSE_ROW] = 0.5 ; /* ignore rows over 50% dense */
1057  knobs [COLAMD_DENSE_COL] = 0.5 ; /* ignore columns over 50% dense */
1058 }
#define COLAMD_DENSE_COL
Definition: colamd.h:123
#define COLAMD_KNOBS
Definition: colamd.h:114
#define COLAMD_DENSE_ROW
Definition: colamd.h:120
long int integer
Definition: colamd.c:51
integer mbdyn_symamd ( integer  n,
integer  A[],
integer  p[],
integer  perm[],
double  knobs[20],
integer  stats[20],
void *(*)(size_t, size_t)  allocate,
void(*)(void *)  release 
)

Definition at line 1066 of file colamd.c.

References ASSERT, COLAMD_DEFRAG_COUNT, COLAMD_DENSE_COL, COLAMD_DENSE_ROW, COLAMD_ERROR_A_not_present, COLAMD_ERROR_col_length_negative, COLAMD_ERROR_internal_error, COLAMD_ERROR_ncol_negative, COLAMD_ERROR_nnz_negative, COLAMD_ERROR_out_of_memory, COLAMD_ERROR_p0_nonzero, COLAMD_ERROR_p_not_present, COLAMD_ERROR_row_index_out_of_bounds, COLAMD_INFO1, COLAMD_INFO2, COLAMD_INFO3, COLAMD_KNOBS, COLAMD_OK, COLAMD_OK_BUT_JUMBLED, COLAMD_STATS, COLAMD_STATUS, count, DEBUG0, DEBUG1, FALSE, mbdyn_colamd(), mbdyn_colamd_recommended(), mbdyn_colamd_set_defaults(), and TRUE.

1082 {
1083  /* === Local variables ================================================== */
1084 
1085  integer *count ; /* length of each column of M, and col pointer*/
1086  integer *mark ; /* mark array for finding duplicate entries */
1087  integer *M ; /* row indices of matrix M */
1088  integer Mlen ; /* length of M */
1089  integer n_row ; /* number of rows in M */
1090  integer nnz ; /* number of entries in A */
1091  integer i ; /* row index of A */
1092  integer j ; /* column index of A */
1093  integer k ; /* row index of M */
1094  integer mnz ; /* number of nonzeros in M */
1095  integer pp ; /* index into a column of A */
1096  integer last_row ; /* last row seen in the current column */
1097  integer length ; /* number of nonzeros in a column */
1098 
1099  double cknobs [COLAMD_KNOBS] ; /* knobs for colamd */
1100  double default_knobs [COLAMD_KNOBS] ; /* default knobs for colamd */
1101  integer cstats [COLAMD_STATS] ; /* colamd stats */
1102 
1103 #ifndef NDEBUG
1104  colamd_get_debug ("symamd") ;
1105 #endif /* NDEBUG */
1106 
1107  /* === Check the input arguments ======================================== */
1108 
1109  if (!stats)
1110  {
1111  DEBUG0 (("symamd: stats not present\n")) ;
1112  return (FALSE) ;
1113  }
1114  for (i = 0 ; i < COLAMD_STATS ; i++)
1115  {
1116  stats [i] = 0 ;
1117  }
1118  stats [COLAMD_STATUS] = COLAMD_OK ;
1119  stats [COLAMD_INFO1] = -1 ;
1120  stats [COLAMD_INFO2] = -1 ;
1121 
1122  if (!A)
1123  {
1125  DEBUG0 (("symamd: A not present\n")) ;
1126  return (FALSE) ;
1127  }
1128 
1129  if (!p) /* p is not present */
1130  {
1132  DEBUG0 (("symamd: p not present\n")) ;
1133  return (FALSE) ;
1134  }
1135 
1136  if (n < 0) /* n must be >= 0 */
1137  {
1139  stats [COLAMD_INFO1] = n ;
1140  DEBUG0 (("symamd: n negative %d\n", n)) ;
1141  return (FALSE) ;
1142  }
1143 
1144  nnz = p [n] ;
1145  if (nnz < 0) /* nnz must be >= 0 */
1146  {
1148  stats [COLAMD_INFO1] = nnz ;
1149  DEBUG0 (("symamd: number of entries negative %d\n", nnz)) ;
1150  return (FALSE) ;
1151  }
1152 
1153  if (p [0] != 0)
1154  {
1156  stats [COLAMD_INFO1] = p [0] ;
1157  DEBUG0 (("symamd: p[0] not zero %d\n", p [0])) ;
1158  return (FALSE) ;
1159  }
1160 
1161  /* === If no knobs, set default knobs =================================== */
1162 
1163  if (!knobs)
1164  {
1165  mbdyn_colamd_set_defaults (default_knobs) ;
1166  knobs = default_knobs ;
1167  }
1168 
1169  /* === Allocate count and mark ========================================== */
1170 
1171  count = (integer *) ((*allocate) (n+1, sizeof (int))) ;
1172  if (!count)
1173  {
1175  DEBUG0 (("symamd: allocate count (size %d) failed\n", n+1)) ;
1176  return (FALSE) ;
1177  }
1178 
1179  mark = (integer *) ((*allocate) (n+1, sizeof (int))) ;
1180  if (!mark)
1181  {
1183  (*release) ((void *) count) ;
1184  DEBUG0 (("symamd: allocate mark (size %d) failed\n", n+1)) ;
1185  return (FALSE) ;
1186  }
1187 
1188  /* === Compute column counts of M, check if A is valid ================== */
1189 
1190  stats [COLAMD_INFO3] = 0 ; /* number of duplicate or unsorted row indices*/
1191 
1192  for (i = 0 ; i < n ; i++)
1193  {
1194  mark [i] = -1 ;
1195  }
1196 
1197  for (j = 0 ; j < n ; j++)
1198  {
1199  last_row = -1 ;
1200 
1201  length = p [j+1] - p [j] ;
1202  if (length < 0)
1203  {
1204  /* column pointers must be non-decreasing */
1206  stats [COLAMD_INFO1] = j ;
1207  stats [COLAMD_INFO2] = length ;
1208  (*release) ((void *) count) ;
1209  (*release) ((void *) mark) ;
1210  DEBUG0 (("symamd: col %d negative length %d\n", j, length)) ;
1211  return (FALSE) ;
1212  }
1213 
1214  for (pp = p [j] ; pp < p [j+1] ; pp++)
1215  {
1216  i = A [pp] ;
1217  if (i < 0 || i >= n)
1218  {
1219  /* row index i, in column j, is out of bounds */
1221  stats [COLAMD_INFO1] = j ;
1222  stats [COLAMD_INFO2] = i ;
1223  stats [COLAMD_INFO3] = n ;
1224  (*release) ((void *) count) ;
1225  (*release) ((void *) mark) ;
1226  DEBUG0 (("symamd: row %d col %d out of bounds\n", i, j)) ;
1227  return (FALSE) ;
1228  }
1229 
1230  if (i <= last_row || mark [i] == j)
1231  {
1232  /* row index is unsorted or repeated (or both), thus col */
1233  /* is jumbled. This is a notice, not an error condition. */
1235  stats [COLAMD_INFO1] = j ;
1236  stats [COLAMD_INFO2] = i ;
1237  (stats [COLAMD_INFO3]) ++ ;
1238  DEBUG1 (("symamd: row %d col %d unsorted/duplicate\n", i, j)) ;
1239  }
1240 
1241  if (i > j && mark [i] != j)
1242  {
1243  /* row k of M will contain column indices i and j */
1244  count [i]++ ;
1245  count [j]++ ;
1246  }
1247 
1248  /* mark the row as having been seen in this column */
1249  mark [i] = j ;
1250 
1251  last_row = i ;
1252  }
1253  }
1254 
1255  if (stats [COLAMD_STATUS] == COLAMD_OK)
1256  {
1257  /* if there are no duplicate entries, then mark is no longer needed */
1258  (*release) ((void *) mark) ;
1259  }
1260 
1261  /* === Compute column pointers of M ===================================== */
1262 
1263  /* use output permutation, perm, for column pointers of M */
1264  perm [0] = 0 ;
1265  for (j = 1 ; j <= n ; j++)
1266  {
1267  perm [j] = perm [j-1] + count [j-1] ;
1268  }
1269  for (j = 0 ; j < n ; j++)
1270  {
1271  count [j] = perm [j] ;
1272  }
1273 
1274  /* === Construct M ====================================================== */
1275 
1276  mnz = perm [n] ;
1277  n_row = mnz / 2 ;
1278  Mlen = mbdyn_colamd_recommended (mnz, n_row, n) ;
1279  M = (integer *) ((*allocate) (Mlen, sizeof (int))) ;
1280  DEBUG0 (("symamd: M is %d-by-%d with %d entries, Mlen = %d\n",
1281  n_row, n, mnz, Mlen)) ;
1282 
1283  if (!M)
1284  {
1286  (*release) ((void *) count) ;
1287  (*release) ((void *) mark) ;
1288  DEBUG0 (("symamd: allocate M (size %d) failed\n", Mlen)) ;
1289  return (FALSE) ;
1290  }
1291 
1292  k = 0 ;
1293 
1294  if (stats [COLAMD_STATUS] == COLAMD_OK)
1295  {
1296  /* Matrix is OK */
1297  for (j = 0 ; j < n ; j++)
1298  {
1299  ASSERT (p [j+1] - p [j] >= 0) ;
1300  for (pp = p [j] ; pp < p [j+1] ; pp++)
1301  {
1302  i = A [pp] ;
1303  ASSERT (i >= 0 && i < n) ;
1304  if (i > j)
1305  {
1306  /* row k of M contains column indices i and j */
1307  M [count [i]++] = k ;
1308  M [count [j]++] = k ;
1309  k++ ;
1310  }
1311  }
1312  }
1313  }
1314  else
1315  {
1316  /* Matrix is jumbled. Do not add duplicates to M. Unsorted cols OK. */
1317  DEBUG0 (("symamd: Duplicates in A.\n")) ;
1318  for (i = 0 ; i < n ; i++)
1319  {
1320  mark [i] = -1 ;
1321  }
1322  for (j = 0 ; j < n ; j++)
1323  {
1324  ASSERT (p [j+1] - p [j] >= 0) ;
1325  for (pp = p [j] ; pp < p [j+1] ; pp++)
1326  {
1327  i = A [pp] ;
1328  ASSERT (i >= 0 && i < n) ;
1329  if (i > j && mark [i] != j)
1330  {
1331  /* row k of M contains column indices i and j */
1332  M [count [i]++] = k ;
1333  M [count [j]++] = k ;
1334  k++ ;
1335  mark [i] = j ;
1336  }
1337  }
1338  }
1339  (*release) ((void *) mark) ;
1340  }
1341 
1342  /* count and mark no longer needed */
1343  (*release) ((void *) count) ;
1344  ASSERT (k == n_row) ;
1345 
1346  /* === Adjust the knobs for M =========================================== */
1347 
1348  for (i = 0 ; i < COLAMD_KNOBS ; i++)
1349  {
1350  cknobs [i] = knobs [i] ;
1351  }
1352 
1353  /* there are no dense rows in M */
1354  cknobs [COLAMD_DENSE_ROW] = 1.0 ;
1355 
1356  if (n_row != 0 && n < n_row)
1357  {
1358  /* On input, the knob is a fraction of 1..n, the number of rows of A. */
1359  /* Convert it to a fraction of 1..n_row, of the number of rows of M. */
1360  cknobs [COLAMD_DENSE_COL] = (knobs [COLAMD_DENSE_ROW] * n) / n_row ;
1361  }
1362  else
1363  {
1364  /* no dense columns in M */
1365  cknobs [COLAMD_DENSE_COL] = 1.0 ;
1366  }
1367 
1368  DEBUG0 (("symamd: dense col knob for M: %g\n", cknobs [COLAMD_DENSE_COL])) ;
1369 
1370  /* === Order the columns of M =========================================== */
1371 
1372  if (!mbdyn_colamd (n_row, n, Mlen, M, perm, cknobs, cstats))
1373  {
1374  /* This "cannot" happen, unless there is a bug in the code. */
1376  (*release) ((void *) M) ;
1377  DEBUG0 (("symamd: internal error!\n")) ;
1378  return (FALSE) ;
1379  }
1380 
1381  /* Note that the output permutation is now in perm */
1382 
1383  /* === get the statistics for symamd from colamd ======================== */
1384 
1385  /* note that a dense column in colamd means a dense row and col in symamd */
1386  stats [COLAMD_DENSE_ROW] = cstats [COLAMD_DENSE_COL] ;
1387  stats [COLAMD_DENSE_COL] = cstats [COLAMD_DENSE_COL] ;
1388  stats [COLAMD_DEFRAG_COUNT] = cstats [COLAMD_DEFRAG_COUNT] ;
1389 
1390  /* === Free M =========================================================== */
1391 
1392  (*release) ((void *) M) ;
1393  DEBUG0 (("symamd: done.\n")) ;
1394  return (TRUE) ;
1395 
1396 }
#define COLAMD_DEFRAG_COUNT
Definition: colamd.h:126
#define COLAMD_INFO2
Definition: colamd.h:133
#define COLAMD_ERROR_col_length_negative
Definition: colamd.h:146
#define COLAMD_INFO3
Definition: colamd.h:134
void mbdyn_colamd_set_defaults(double knobs[20])
Definition: colamd.c:1038
#define COLAMD_STATS
Definition: colamd.h:117
#define COLAMD_DENSE_COL
Definition: colamd.h:123
#define COLAMD_ERROR_p_not_present
Definition: colamd.h:140
#define COLAMD_ERROR_A_not_present
Definition: colamd.h:139
#define TRUE
Definition: colamd.c:759
#define COLAMD_KNOBS
Definition: colamd.h:114
#define COLAMD_ERROR_internal_error
Definition: colamd.h:149
integer mbdyn_colamd_recommended(integer nnz, integer n_row, integer n_col)
Definition: colamd.c:1004
integer mbdyn_colamd(integer n_row, integer n_col, integer Alen, integer A[], integer p[], double knobs[20], integer stats[20])
Definition: colamd.c:1411
#define COLAMD_OK
Definition: colamd.h:137
static int count
Definition: modules.cc:41
#define COLAMD_OK_BUT_JUMBLED
Definition: colamd.h:138
#define ASSERT(expression)
Definition: colamd.c:977
#define COLAMD_DENSE_ROW
Definition: colamd.h:120
#define COLAMD_INFO1
Definition: colamd.h:132
#define COLAMD_ERROR_ncol_negative
Definition: colamd.h:142
#define COLAMD_ERROR_row_index_out_of_bounds
Definition: colamd.h:147
#define FALSE
Definition: colamd.c:763
#define COLAMD_ERROR_out_of_memory
Definition: colamd.h:148
#define DEBUG0(params)
Definition: colamd.c:971
long int integer
Definition: colamd.c:51
#define COLAMD_STATUS
Definition: colamd.h:129
#define COLAMD_ERROR_nnz_negative
Definition: colamd.h:143
#define DEBUG1(params)
Definition: colamd.c:972
#define COLAMD_ERROR_p0_nonzero
Definition: colamd.h:144

Here is the call graph for this function:

void mbdyn_symamd_report ( integer  stats[20])

Definition at line 1583 of file colamd.c.

References print_report().

1586 {
1587  print_report ("symamd", stats) ;
1588 }
static void print_report(char *method, integer stats[20])
Definition: colamd.c:3091

Here is the call graph for this function:

static void order_children ( integer  n_col,
mbdyn_Colamd_Col  Col[],
integer  p[] 
)
static

Definition at line 2670 of file colamd.c.

References ASSERT, c, COL_IS_DEAD, COL_IS_DEAD_PRINCIPAL, EMPTY, order, mbdyn_Colamd_Col::order, mbdyn_Colamd_Col::parent, mbdyn_Colamd_Col::shared1, and mbdyn_Colamd_Col::shared2.

Referenced by mbdyn_colamd().

2677 {
2678  /* === Local variables ================================================== */
2679 
2680  integer i ; /* loop counter for all columns */
2681  integer c ; /* column index */
2682  integer parent ; /* index of column's parent */
2683  integer order ; /* column's order */
2684 
2685  /* === Order each non-principal column ================================== */
2686 
2687  for (i = 0 ; i < n_col ; i++)
2688  {
2689  /* find an un-ordered non-principal column */
2690  ASSERT (COL_IS_DEAD (i)) ;
2691  if (!COL_IS_DEAD_PRINCIPAL (i) && Col [i].shared2.order == EMPTY)
2692  {
2693  parent = i ;
2694  /* once found, find its principal parent */
2695  do
2696  {
2697  parent = Col [parent].shared1.parent ;
2698  } while (!COL_IS_DEAD_PRINCIPAL (parent)) ;
2699 
2700  /* now, order all un-ordered non-principal columns along path */
2701  /* to this parent. collapse tree at the same time */
2702  c = i ;
2703  /* get order of parent */
2704  order = Col [parent].shared2.order ;
2705 
2706  do
2707  {
2708  ASSERT (Col [c].shared2.order == EMPTY) ;
2709 
2710  /* order this column */
2711  Col [c].shared2.order = order++ ;
2712  /* collaps tree */
2713  Col [c].shared1.parent = parent ;
2714 
2715  /* get immediate parent of this column */
2716  c = Col [c].shared1.parent ;
2717 
2718  /* continue until we hit an ordered column. There are */
2719  /* guarranteed not to be anymore unordered columns */
2720  /* above an ordered column */
2721  } while (Col [c].shared2.order == EMPTY) ;
2722 
2723  /* re-order the super_col parent to largest order for this group */
2724  Col [parent].shared2.order = order ;
2725  }
2726  }
2727 
2728  /* === Generate the permutation ========================================= */
2729 
2730  for (c = 0 ; c < n_col ; c++)
2731  {
2732  p [Col [c].shared2.order] = c ;
2733  }
2734 }
integer parent
Definition: colamd.h:168
union mbdyn_Colamd_Col::@1 shared2
enum @55 order
union mbdyn_Colamd_Col::@0 shared1
#define COL_IS_DEAD_PRINCIPAL(c)
Definition: colamd.c:784
#define COL_IS_DEAD(c)
Definition: colamd.c:782
#define ASSERT(expression)
Definition: colamd.c:977
static std::stack< cleanup * > c
Definition: cleanup.cc:59
integer order
Definition: colamd.h:174
#define EMPTY
Definition: colamd.c:768
long int integer
Definition: colamd.c:51
static void print_report ( char *  method,
integer  stats[20] 
)
static

Definition at line 3091 of file colamd.c.

References COLAMD_DEFRAG_COUNT, COLAMD_DENSE_COL, COLAMD_DENSE_ROW, COLAMD_ERROR_A_not_present, COLAMD_ERROR_A_too_small, COLAMD_ERROR_col_length_negative, COLAMD_ERROR_internal_error, COLAMD_ERROR_ncol_negative, COLAMD_ERROR_nnz_negative, COLAMD_ERROR_nrow_negative, COLAMD_ERROR_out_of_memory, COLAMD_ERROR_p0_nonzero, COLAMD_ERROR_p_not_present, COLAMD_ERROR_row_index_out_of_bounds, COLAMD_INFO1, COLAMD_INFO2, COLAMD_INFO3, COLAMD_OK, COLAMD_OK_BUT_JUMBLED, COLAMD_STATUS, INDEX, and PRINTF.

Referenced by mbdyn_colamd_report(), and mbdyn_symamd_report().

3095 {
3096 
3097  integer i1, i2, i3 ;
3098 
3099  if (!stats)
3100  {
3101  PRINTF ("%s: No statistics available.\n", method) ;
3102  return ;
3103  }
3104 
3105  i1 = stats [COLAMD_INFO1] ;
3106  i2 = stats [COLAMD_INFO2] ;
3107  i3 = stats [COLAMD_INFO3] ;
3108 
3109  if (stats [COLAMD_STATUS] >= 0)
3110  {
3111  PRINTF ("%s: OK. ", method) ;
3112  }
3113  else
3114  {
3115  PRINTF ("%s: ERROR. ", method) ;
3116  }
3117 
3118  switch (stats [COLAMD_STATUS])
3119  {
3120 
3121  case COLAMD_OK_BUT_JUMBLED:
3122 
3123  PRINTF ("Matrix has unsorted or duplicate row indices.\n") ;
3124 
3125  PRINTF ("%s: number of duplicate or out-of-order row indices: %d\n",
3126  method, i3) ;
3127 
3128  PRINTF ("%s: last seen duplicate or out-of-order row index: %d\n",
3129  method, INDEX (i2)) ;
3130 
3131  PRINTF ("%s: last seen in column: %d",
3132  method, INDEX (i1)) ;
3133 
3134  /* no break - fall through to next case instead */
3135 
3136  case COLAMD_OK:
3137 
3138  PRINTF ("\n") ;
3139 
3140  PRINTF ("%s: number of dense or empty rows ignored: %d\n",
3141  method, stats [COLAMD_DENSE_ROW]) ;
3142 
3143  PRINTF ("%s: number of dense or empty columns ignored: %d\n",
3144  method, stats [COLAMD_DENSE_COL]) ;
3145 
3146  PRINTF ("%s: number of garbage collections performed: %d\n",
3147  method, stats [COLAMD_DEFRAG_COUNT]) ;
3148  break ;
3149 
3151 
3152  PRINTF ("Array A (row indices of matrix) not present.\n") ;
3153  break ;
3154 
3156 
3157  PRINTF ("Array p (column pointers for matrix) not present.\n") ;
3158  break ;
3159 
3161 
3162  PRINTF ("Invalid number of rows (%d).\n", i1) ;
3163  break ;
3164 
3166 
3167  PRINTF ("Invalid number of columns (%d).\n", i1) ;
3168  break ;
3169 
3171 
3172  PRINTF ("Invalid number of nonzero entries (%d).\n", i1) ;
3173  break ;
3174 
3176 
3177  PRINTF ("Invalid column pointer, p [0] = %d, must be zero.\n", i1) ;
3178  break ;
3179 
3181 
3182  PRINTF ("Array A too small.\n") ;
3183  PRINTF (" Need Alen >= %d, but given only Alen = %d.\n",
3184  i1, i2) ;
3185  break ;
3186 
3188 
3189  PRINTF
3190  ("Column %d has a negative number of nonzero entries (%d).\n",
3191  INDEX (i1), i2) ;
3192  break ;
3193 
3195 
3196  PRINTF
3197  ("Row index (row %d) out of bounds (%d to %d) in column %d.\n",
3198  INDEX (i2), INDEX (0), INDEX (i3-1), INDEX (i1)) ;
3199  break ;
3200 
3202 
3203  PRINTF ("Out of memory.\n") ;
3204  break ;
3205 
3207 
3208  /* if this happens, there is a bug in the code */
3209  PRINTF
3210  ("Internal error! Please contact authors (davis@cise.ufl.edu).\n") ;
3211  break ;
3212  }
3213 }
#define COLAMD_DEFRAG_COUNT
Definition: colamd.h:126
#define COLAMD_INFO2
Definition: colamd.h:133
#define COLAMD_ERROR_col_length_negative
Definition: colamd.h:146
#define COLAMD_INFO3
Definition: colamd.h:134
#define COLAMD_DENSE_COL
Definition: colamd.h:123
#define COLAMD_ERROR_p_not_present
Definition: colamd.h:140
#define COLAMD_ERROR_A_too_small
Definition: colamd.h:145
#define COLAMD_ERROR_A_not_present
Definition: colamd.h:139
#define INDEX(i)
Definition: colamd.c:809
#define COLAMD_ERROR_internal_error
Definition: colamd.h:149
#define COLAMD_OK
Definition: colamd.h:137
#define COLAMD_OK_BUT_JUMBLED
Definition: colamd.h:138
#define COLAMD_DENSE_ROW
Definition: colamd.h:120
#define COLAMD_INFO1
Definition: colamd.h:132
#define COLAMD_ERROR_ncol_negative
Definition: colamd.h:142
#define COLAMD_ERROR_row_index_out_of_bounds
Definition: colamd.h:147
#define COLAMD_ERROR_nrow_negative
Definition: colamd.h:141
#define PRINTF
Definition: colamd.c:806
#define COLAMD_ERROR_out_of_memory
Definition: colamd.h:148
long int integer
Definition: colamd.c:51
#define COLAMD_STATUS
Definition: colamd.h:129
#define COLAMD_ERROR_nnz_negative
Definition: colamd.h:143
#define COLAMD_ERROR_p0_nonzero
Definition: colamd.h:144