FDLA and FMMC solutions for a 64-node, 95-edge cut-grid graph

% S. Boyd, et. al., "Convex Optimization of Graph Laplacian Eigenvalues"
% ICM'06 talk examples (www.stanford.edu/~boyd/cvx_opt_graph_lapl_eigs.html)
% Written for CVX by Almir Mutapcic 08/29/06
% (figures are generated)
%
% In this example we consider a graph described by the incidence matrix A.
% Each edge has a weight W_i, and we optimize various functions of the
% edge weights as described in the referenced paper; in particular,
%
% - the fastest distributed linear averaging (FDLA) problem (fdla.m)
% - the fastest mixing Markov chain (FMMC) problem (fmmc.m)
%
% Then we compare these solutions to the heuristics listed below:
%
% - maximum-degree heuristic (max_deg.m)
% - constant weights that yield fastest averaging (best_const.m)
% - Metropolis-Hastings heuristic (mh.m)

% generate a cut-grid graph example
[A,xy] = cut_grid_data;

% Compute edge weights: some optimal, some based on heuristics
fprintf(1,'WARNING: The optimal weight computations take some time...\n');
[n,m] = size(A);

[ w_fdla, rho_fdla ] = fdla(A);
[ w_fmmc, rho_fmmc ] = fmmc(A);
[ w_md,   rho_md   ] = max_deg(A);
[ w_bc,   rho_bc   ] = best_const(A);
[ w_mh,   rho_mh   ] = mh(A);

tau_fdla = 1/log(1/rho_fdla);
tau_fmmc = 1/log(1/rho_fmmc);
tau_md   = 1/log(1/rho_md);
tau_bc   = 1/log(1/rho_bc);
tau_mh   = 1/log(1/rho_mh);

fprintf(1,'\nResults:\n');
fprintf(1,'FDLA weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_fdla,tau_fdla);
fprintf(1,'FMMC weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_fmmc,tau_fmmc);
fprintf(1,'M-H weights:\t\t rho = %5.4f \t tau = %5.4f\n',rho_mh,tau_mh);
fprintf(1,'MAX_DEG weights:\t rho = %5.4f \t tau = %5.4f\n',rho_md,tau_md);
fprintf(1,'BEST_CONST weights:\t rho = %5.4f \t tau = %5.4f\n',rho_bc,tau_bc);

% plot results
figure(1), clf
plotgraph(A,xy,w_fdla);
text(0.425,1.05,'FDLA optimal weights')

figure(2), clf
plotgraph(A,xy,w_fmmc);
text(0.425,1.05,'FMMC optimal weights')

figure(3), clf
plotgraph(A,xy,w_md);
text(0.375,1.05,'Max degree optimal weights')

figure(4), clf
plotgraph(A,xy,w_bc);
text(0.375,1.05,'Best constant optimal weights')

figure(5), clf
plotgraph(A,xy,w_mh);
text(0.3,1.05,'Metropolis-Hastings optimal weights')
WARNING: The optimal weight computations take some time...
 
Calling SeDuMi: 4166 variables (6 free), 4070 equality constraints
------------------------------------------------------------------------
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 4070, order n = 131, dim = 8200, blocks = 4
nnz(A) = 4553 + 0, nnz(ADA) = 8884742, nnz(L) = 4444406
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            2.24E-001 0.000
  1 :  1.21E+001 1.45E-002 0.000 0.0647 0.9900 0.9900  -0.68  1  1  1.3E+000
  2 :  3.41E+000 6.17E-003 0.000 0.4256 0.9000 0.9000   2.14  1  1  3.1E-001
  3 :  1.14E+000 2.77E-003 0.000 0.4483 0.9000 0.9000   4.54  1  1  4.6E-002
  4 :  1.02E+000 9.92E-004 0.000 0.3585 0.9000 0.9000   1.30  1  1  1.6E-002
  5 :  1.00E+000 2.92E-004 0.000 0.2942 0.9000 0.9000   1.04  1  1  4.6E-003
  6 :  9.92E-001 1.50E-005 0.000 0.0516 0.9081 0.9000   1.02  1  1  7.4E-004
  7 :  9.89E-001 4.20E-006 0.000 0.2790 0.9000 0.8584   1.00  1  1  2.0E-004
  8 :  9.89E-001 1.55E-006 0.000 0.3702 0.9000 0.7890   1.00  1  1  7.5E-005
  9 :  9.88E-001 4.84E-007 0.000 0.3113 0.9000 0.9000   1.00  1  1  2.3E-005
 10 :  9.88E-001 1.22E-007 0.000 0.2525 0.9000 0.9000   1.00  1  1  5.9E-006
 11 :  9.88E-001 8.82E-009 0.160 0.0723 0.9903 0.9900   1.00  1  1  5.0E-007
 12 :  9.88E-001 1.32E-009 0.000 0.1500 0.9195 0.9000   1.00  1  1  1.0E-007
 13 :  9.88E-001 5.48E-011 0.207 0.0414 0.9900 0.9900   1.00  1  1  4.2E-009

iter seconds digits       c*x               b*y
 13    363.3   Inf  9.8829189011e-001  9.8829190041e-001
|Ax-b| =  6.3e-009, [Ay-c]_+ =  1.8E-009, |x|= 1.4e+001, |y|= 1.3e+000

Detailed timing (sec)
   Pre          IPM          Post
8.462E+000    3.633E+002    1.001E-001    
Max-norms: ||b||=9.843750e-001, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 48.5623.
------------------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.988292
 
Calling SeDuMi: 4320 variables (1 free), 4224 equality constraints
------------------------------------------------------------------------
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 4224, order n = 290, dim = 8354, blocks = 4
nnz(A) = 4862 + 0, nnz(ADA) = 8662492, nnz(L) = 4357082
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            2.16E-001 0.000
  1 :  2.76E-001 7.40E-002 0.000 0.3426 0.9000 0.9000   2.60  1  1  2.1E+000
  2 :  8.80E-001 1.77E-002 0.000 0.2397 0.9000 0.9000   1.69  1  1  3.6E-001
  3 :  9.98E-001 6.10E-004 0.000 0.0344 0.9900 0.9900   1.21  1  1  1.1E-002
  4 :  9.93E-001 1.60E-004 0.000 0.2618 0.9000 0.9000   1.04  1  1  2.8E-003
  5 :  9.91E-001 4.36E-005 0.000 0.2729 0.9000 0.9000   1.02  1  1  7.6E-004
  6 :  9.90E-001 1.63E-005 0.000 0.3734 0.9022 0.9000   1.03  1  1  3.2E-004
  7 :  9.90E-001 2.31E-006 0.000 0.1421 0.9350 0.9000   1.03  1  1  1.0E-004
  8 :  9.89E-001 6.65E-007 0.000 0.2881 0.9270 0.9000   1.02  1  1  3.7E-005
  9 :  9.89E-001 1.31E-007 0.000 0.1967 0.9503 0.9000   1.01  1  1  1.2E-005
 10 :  9.89E-001 4.32E-008 0.000 0.3303 0.9000 0.9085   1.01  1  1  3.9E-006
 11 :  9.89E-001 1.95E-008 0.000 0.4516 0.9312 0.9000   1.01  1  1  1.7E-006
 12 :  9.89E-001 1.03E-008 0.000 0.5274 0.9482 0.9000   1.00  1  1  9.0E-007
 13 :  9.89E-001 2.11E-009 0.000 0.2045 0.9000 0.9107   1.00  2  2  1.9E-007
 14 :  9.89E-001 7.02E-010 0.000 0.3336 0.9000 0.9023   1.00  2  2  6.4E-008
 15 :  9.89E-001 2.60E-010 0.000 0.3707 0.0000 0.9000   1.00  2  2  2.8E-008
 16 :  9.89E-001 9.54E-011 0.000 0.3665 0.9000 0.6588   1.00  2  2  1.1E-008

iter seconds digits       c*x               b*y
 16    426.3   Inf  9.8882651338e-001  9.8882651703e-001
|Ax-b| =  1.2e-009, [Ay-c]_+ =  5.6E-009, |x|= 1.4e+001, |y|= 1.4e+000

Detailed timing (sec)
   Pre          IPM          Post
9.243E+000    4.263E+002    1.001E-002    
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 44.4774.
------------------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.988827

Results:
FDLA weights:		 rho = 0.9883 	 tau = 84.9099
FMMC weights:		 rho = 0.9888 	 tau = 88.9966
M-H weights:		 rho = 0.9917 	 tau = 120.2442
MAX_DEG weights:	 rho = 0.9927 	 tau = 136.7523
BEST_CONST weights:	 rho = 0.9921 	 tau = 126.3450