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
[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')
 
Calling sedumi: 4184 variables, 120 equality constraints
   For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 120, order n = 131, dim = 8218, blocks = 4
nnz(A) = 699 + 0, nnz(ADA) = 14400, nnz(L) = 7260
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.32E+02 0.000
  1 :  -5.40E+00 8.97E+00 0.000 0.0680 0.9900 0.9900  -0.65  1  1  5.1E+01
  2 :  -3.09E+00 3.82E+00 0.000 0.4260 0.9000 0.9000   2.14  1  1  1.2E+01
  3 :  -1.05E+00 1.67E+00 0.000 0.4369 0.9000 0.9000   4.41  1  1  1.8E+00
  4 :  -9.93E-01 5.92E-01 0.000 0.3547 0.9000 0.9000   1.30  1  1  5.9E-01
  5 :  -9.98E-01 1.74E-01 0.000 0.2935 0.9000 0.9000   1.03  1  1  1.7E-01
  6 :  -9.91E-01 3.55E-02 0.000 0.2044 0.9000 0.8709   1.02  1  1  3.6E-02
  7 :  -9.89E-01 8.25E-03 0.000 0.2322 0.9056 0.9000   1.01  1  1  8.1E-03
  8 :  -9.88E-01 2.44E-03 0.000 0.2955 0.9129 0.9000   1.00  1  1  2.3E-03
  9 :  -9.88E-01 7.84E-04 0.000 0.3217 0.9038 0.9000   1.00  1  1  7.5E-04
 10 :  -9.88E-01 1.90E-04 0.000 0.2417 0.9023 0.9000   1.00  1  1  1.8E-04
 11 :  -9.88E-01 1.82E-05 0.078 0.0959 0.9900 0.9902   1.00  1  1  1.7E-05
 12 :  -9.88E-01 4.45E-06 0.000 0.2447 0.9000 0.9124   1.00  2  2  4.3E-06
 13 :  -9.88E-01 8.04E-07 0.000 0.1806 0.9000 0.9063   1.00  2  2  7.7E-07
 14 :  -9.88E-01 1.47E-07 0.000 0.1826 0.9000 0.9077   1.00  7  7  1.4E-07
 15 :  -9.88E-01 1.53E-08 0.425 0.1041 0.9900 0.9900   1.00 48 46  1.5E-08

iter seconds digits       c*x               b*y
 15      1.4   9.1 -9.8829188306e-01 -9.8829188380e-01
|Ax-b| =   1.4e-08, [Ay-c]_+ =   4.6E-11, |x|=  1.8e+00, |y|=  6.8e+00

Detailed timing (sec)
   Pre          IPM          Post
2.000E-02    1.430E+00    1.000E-02    
Max-norms: ||b||=1, ||c|| = 9.843750e-01,
Cholesky |add|=0, |skip| = 22, ||L.L|| = 57279.1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.988292
 
Calling sedumi: 4368 variables, 145 equality constraints
   For improved efficiency, sedumi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 145, order n = 290, dim = 8402, blocks = 4
nnz(A) = 910 + 0, nnz(ADA) = 21025, nnz(L) = 10585
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.33E+02 0.000
  1 :  -6.90E-01 5.51E+01 0.000 0.4155 0.9000 0.9000   2.46  1  1  7.3E+01
  2 :  -9.46E-01 1.35E+01 0.000 0.2459 0.9000 0.9000   1.80  1  1  1.3E+01
  3 :  -1.00E+00 1.01E+00 0.000 0.0742 0.9900 0.9900   1.25  1  1  8.4E-01
  4 :  -9.93E-01 3.60E-01 0.000 0.3577 0.9000 0.9000   1.05  1  1  3.0E-01
  5 :  -9.93E-01 7.88E-02 0.000 0.2192 0.9000 0.9000   1.01  1  1  6.5E-02
  6 :  -9.91E-01 2.34E-02 0.000 0.2968 0.9029 0.9000   1.02  1  1  1.9E-02
  7 :  -9.90E-01 1.11E-02 0.000 0.4749 0.9000 0.9068   1.03  1  1  8.9E-03
  8 :  -9.89E-01 5.97E-03 0.000 0.5369 0.9000 0.9393   1.03  1  1  4.9E-03
  9 :  -9.89E-01 2.88E-03 0.000 0.4822 0.9000 0.9233   1.01  1  1  2.4E-03
 10 :  -9.89E-01 1.60E-03 0.000 0.5557 0.9000 0.9000   1.01  1  1  1.3E-03
 11 :  -9.89E-01 4.66E-04 0.000 0.2918 0.9161 0.9000   1.01  1  1  3.7E-04
 12 :  -9.89E-01 2.10E-04 0.000 0.4499 0.9000 0.8811   1.01  1  1  1.7E-04
 13 :  -9.89E-01 9.92E-05 0.000 0.4727 0.9000 0.5906   1.01  2  2  8.1E-05
 14 :  -9.89E-01 2.73E-05 0.000 0.2748 0.9155 0.9000   1.00  2  2  2.1E-05
 15 :  -9.89E-01 1.11E-05 0.000 0.4079 0.9000 0.9063   1.00  2  2  8.8E-06
 16 :  -9.89E-01 5.03E-06 0.000 0.4523 0.9000 0.7132   1.00  8  8  4.1E-06
 17 :  -9.89E-01 1.55E-06 0.000 0.3080 0.9079 0.9000   1.00 11 11  1.2E-06
 18 :  -9.89E-01 6.37E-07 0.000 0.4111 0.9000 0.8005   1.00 16 16  5.2E-07
 19 :  -9.89E-01 2.32E-07 0.000 0.3648 0.9000 0.8496   1.00 27 27  1.9E-07
 20 :  -9.89E-01 8.77E-08 0.000 0.3776 0.9000 0.9000   1.01 75 77  7.1E-08
Run into numerical problems.

iter seconds digits       c*x               b*y
 20      3.0   Inf -9.8882616673e-01 -9.8882616654e-01
|Ax-b| =   7.1e-08, [Ay-c]_+ =   2.5E-10, |x|=  2.3e+00, |y|=  8.2e+00

Detailed timing (sec)
   Pre          IPM          Post
1.000E-02    3.010E+00    1.000E-02    
Max-norms: ||b||=1, ||c|| = 1.015625e+00,
Cholesky |add|=0, |skip| = 31, ||L.L|| = 12696.9.
------------------------------------------------------------
Status: Inaccurate/Solved
Optimal value (cvx_optval): +0.988826

Results:
FDLA weights:		 rho = 0.9883 	 tau = 84.9099
FMMC weights:		 rho = 0.9888 	 tau = 88.9939
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