Matrix: Schenk/nlpkkt120

Description: Symmetric indefinite KKT matrix, O. Schenk, Univ. of Basel

Schenk/nlpkkt120 graph
(undirected graph drawing)


Schenk/nlpkkt120

  • Home page of the UF Sparse Matrix Collection
  • Matrix group: Schenk
  • Click here for a description of the Schenk group.
  • Click here for a list of all matrices
  • Click here for a list of all matrix groups
  • download as a MATLAB mat-file, file size: 109 MB. Use UFget(1902) or UFget('Schenk/nlpkkt120') in MATLAB.
  • download in Matrix Market format, file size: 157 MB.
  • download in Rutherford/Boeing format, file size: 69 MB.

    Matrix properties
    number of rows3,542,400
    number of columns3,542,400
    nonzeros95,117,792
    structural full rank?yes
    structural rank3,542,400
    # of blocks from dmperm1
    # strongly connected comp.1
    explicit zero entries1,728,000
    nonzero pattern symmetrysymmetric
    numeric value symmetrysymmetric
    typereal
    structuresymmetric
    Cholesky candidate?no
    positive definite?no

    authorO. Schenk, A. Waechter, M. Weiser
    editorT. Davis
    date2008
    kindoptimization problem
    2D/3D problem?no

    Notes:

    Symmetric indefinite KKT matrices, O. Schenk, Univ. of Basel,         
    Switzerland                                                           
    Nonlinear programming problems for a 3D PDE-constrained optimization  
    problem with boundary control as a function of the discretization     
    parameter N using 2nd-order finite difference approximations.         
                                                                          
    O. Schenk, A. W\"achter, and M. Weiser, Inertia Revealing             
    Preconditioning For Large-Scale Nonconvex Constrained Optimization,   
    Technical Report, Unversity of Basel, 2008, submitted.                
                                                                          
    Abstract: Fast nonlinear programming methods following the            
    all-at-once approach usually employ Newton's method for solving       
    linearized Karush-Kuhn-Tucker (KKT) systems. In nonconvex problems,   
    the Newton direction is only guaranteed to be a descent direction if  
    the Hessian of the Lagrange function is positive definite on the      
    nullspace of the active constraints, otherwise some modifications to  
    Newton's method are necessary. This condition can be verified using   
    the signs of the KKT's eigenvalues (inertia), which are usually       
    available from direct solvers for the arising linear saddle point     
    problems. Iterative solvers are mandatory for very large-scale        
    problems, but in general do not provide the inertia. Here we present  
    a preconditioner based on a multilevel incomplete LBL^T               
    factorization, from which an approximation of the inertia can be      
    obtained. The suitability of the heuristics for application in        
    optimization methods is verified on an interior point method applied  
    to the CUTE and COPS test problems, on large-scale 3D PDE-constrained 
    optimal control problems, as well as 3D PDE-constrained optimization  
    in biomedical cancer hyperthermia treatment planning.  The efficiency 
    of the preconditioner is demonstrated on convex and nonconvex         
    problems with 1503 state variables and 1502 control variables, both   
    subject to bound constraints.                                         
    

    Ordering statistics:result
    nnz(chol(P*(A+A'+s*I)*P')) with AMD21,616,014,925
    Cholesky flop count1.2e+15
    nnz(L+U), no partial pivoting, with AMD43,228,487,450
    nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD85,956,355,676
    nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD146,270,001,232

    Note that all matrix statistics (except nonzero pattern symmetry) exclude the 1728000 explicit zero entries.

    For a description of the statistics displayed above, click here.

    Maintained by Tim Davis, last updated 12-Mar-2014.
    Matrix pictures by cspy, a MATLAB function in the CSparse package.
    Matrix graphs by Yifan Hu, AT&T Labs Visualization Group.