Matrix properties
number of rows	1,062,400
number of columns	1,062,400
nonzeros	28,192,672
structural full rank?	yes
structural rank	1,062,400
# of blocks from dmperm	1
# strongly connected comp.	1
explicit zero entries	512,000
nonzero pattern symmetry	symmetric
numeric value symmetry	symmetric
type	real
structure	symmetric
Cholesky candidate?	no
positive definite?	no

author	O. Schenk, A. Waechter, M. Weiser
editor	T. Davis
date	2008
kind	optimization 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 AMD	3,551,309,016
Cholesky flop count	7.8e+13
nnz(L+U), no partial pivoting, with AMD	7,101,555,632
nnz(V) for QR, upper bound nnz(L) for LU, with COLAMD	12,440,046,488
nnz(R) for QR, upper bound nnz(U) for LU, with COLAMD	21,075,362,370

Note that all matrix statistics (except nonzero pattern symmetry) exclude the 512000 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.