PDA

View Full Version : Laplacian, eigen-values and eigen-vectors



The Little Body
11-07-2017, 04:36 PM
Hi,

I want to graphically display eigen-vectors and eigen-values of a matrix

I have begined with this relatively basic 3x3 matrix given at https://www.youtube.com/watch?v=C5uDVyKruFg&t=82

-1 2 2
2 2 -1
2 -1 2


Eigen-values of this matrix are 3 and -3

Eigen vectors of this matrix are

E3 = { 1/2 , 1 , 0 } and { 1/2 , 0 , 1 }

E-3 = { -2 , 1, 1 }


I have used the 3x3 matrix as three 3D coordinates for to display it as a triangle :
(since this is a symetric matrix, no need to handle the row or column major order)

x0 y0 z0
x1 y1 z1
x2 y2 z2

where (x0,y0,z0), (x1,y1,z1) and (x2,y2,z2) are 3D coordinates of the triangle vertices


After I have displayed eigen-vectors as 3D vectors for to try to understand what they really represent in 3D
(for this, I display each eigen-vector as a line in a different color)

But I don't graphically see what is the rapport between the triangle and his eigen-vectors :(
(the only think that I clearly see is that eigen-vectors are orthogonals but this is all)


Here is the basic code that I actually use for to display the triangle and his eigen-vectors



#include <GL/gl.h>
#include <GL/glut.h>

float angle = 0.0f;

float angleInc = 1;

GLfloat vertices[3][3];

void SetVertice( int idx, GLfloat x, GLfloat y, GLfloat z)
{
vertices[idx][0] = x;
vertices[idx][1] = y;
vertices[idx][2] = z;
}

void MakeArrays()
{
SetVertice(0, -1, 2, 2);
SetVertice(1, 2, 2, -1);
SetVertice(2, 2, -1, 2);
}

void DrawAxes()
{
glBegin(GL_LINES);

glColor3f( 1.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 1.0f, 0.0f, 0.0f);

glColor3f(0.0f, 1.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 1.0f, 0.0f);

glColor3f( 0.0f, 0.0f, 1.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 1.0f);

glEnd();
}

void DrawHeigenVectors()
{
glBegin(GL_LINES);

glColor3f( 1.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 0.5f, 1.0f, 0.0f);

glColor3f(0.0f, 1.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 0.5f, 0.0f, 1.0f);

glColor3f( 0.0f, 0.0f, 1.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( -2.0f, 1.0f, 1.0f);

glEnd();
}



void DrawTriangle()
{
int i;

glColor3f(1.0f, 1.0f, 1.0f);

glBegin(GL_TRIANGLES);

for( i = 0 ; i < 3 ; i++)
{
glVertex3fv(vertices[i]);
}

glEnd();
}

void renderScene(void)
{

// Clear Color and Depth Buffers
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

// Reset transformations
glLoadIdentity();

// Set the camera
gluLookAt( 0.0f, 0.0f, 10.0f,
0.0f, 0.0f, 0.0f,
0.0f, 1.0f, 0.0f);

glRotatef(angle, 1.0f, 1.0f, 1.0f);

// DrawAxes();
DrawTriangle();
DrawHeigenVectors();

angle += angleInc;

glutSwapBuffers();
}


void changeSize(int w, int h)
{

// Prevent a divide by zero, when window is too short
// (you cant make a window of zero width).
if (h == 0)
h = 1;

float ratio = w * 1.0 / h;

// Use the Projection Matrix
glMatrixMode(GL_PROJECTION);

// Reset Matrix
glLoadIdentity();

// Set the viewport to be the entire window
glViewport(0, 0, w, h);

// Set the correct perspective.
gluPerspective(45.0f, ratio, 0.1f, 100.0f);

// Get Back to the Modelview
glMatrixMode(GL_MODELVIEW);
}

void keyboardFunc( unsigned char key, int x, int y )
{
switch ( key )
{
case 27: // Escape key

exit (0);
break;


case ' ' : // pause/play key

if( angleInc == 0.0f )
{
angleInc = 1.0f;
}
else
{
angleInc = 0.0f;
}
break;

}

glutPostRedisplay();
}

int main(int argc, char **argv)
{

// init GLUT and create window
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);
glutInitWindowPosition(100,100);
glutInitWindowSize(640,480);
glutCreateWindow("Lighthouse3D- GLUT Tutorial");

// register callbacks
glutDisplayFunc(renderScene);
glutReshapeFunc(changeSize);
glutKeyboardFunc(keyboardFunc);

MakeArrays();

// here is the idle func registration
glutIdleFunc(renderScene);

// enter GLUT event processing cycle
glutMainLoop();

return 0;
}



I plane after to use eigen-values and eigen-vectors for to can handle the spectral compression of a 3D object via his Laplacian matrix


For example, for the very basic example of a triangle :

The Adjency matrix is :

0 1 1
1 0 1
1 1 0

The Degree matrix is :

2 0 0
0 2 0
0 0 2

So, the symetric Laplacian matrix Ls = D - A

2-1 -1
-1 2 -1
-1 -1 2

And the "true" Laplacian matrix is
(this seem the same but divided by 2)

1 -1/2 -1/2
-1/2 1 -1/2
-1/2 -1/2 1


But since I don't see the rapport between the 3D coordinates of a triangle and his eigen-vector,
it's again more difficult to imagine what is the rapport between a Laplacian matrix and his eigen-vectors :(

=> someone can help me a little to understand in more depth how I can represent eigen-values and eigen-vectors on a OpenGL 3D fashion , please ?

The Little Body
11-08-2017, 04:52 PM
For to begin, I have decided to only use a 2x2 matrix for the computation of eigen-values and eigen-vectors with this very simple 2x2 matrix

4 3
-2 -3
(https://en.wikipedia.org/wiki/Eigenvalue_algorithm)




#include <stdio.h>
#include <math.h>
#include <GL/gl.h>
#include <GL/glut.h>

float angle = 0.0f;

float angleInc = 1;

GLfloat vertices[2][2];
GLfloat EigenVectors[2][2];
GLfloat EigenValues[2];


void SetVertice2( int idx, GLfloat x, GLfloat y)
{
vertices[idx][0] = x;
vertices[idx][1] = y;
}

void ComputeVertices2()
{
int i;

SetVertice2(0, 4, 3);
SetVertice2(1, -2, -3);

printf("\nThe 2x2 matrix is \n\n");
for( i = 0 ; i < 2 ; i++)
{
printf("\t %f %f \n", vertices[i][0], vertices[i][1] );
}
}


void SetEigenValue( int idx, GLfloat eigenvalue)
{
EigenValues[idx] = eigenvalue;
}

GLfloat Trace2x2( GLfloat *mat2x2)
{
return mat2x2[0] + mat2x2[3];
}

GLfloat Det2x2( GLfloat *mat2x2)
{
return mat2x2[0] * mat2x2[3] - mat2x2[1] * mat2x2[2];
}




void ComputeEigenValues2()
{
int i;

GLfloat tr = Trace2x2( (GLfloat *) &vertices[0][0] );
GLfloat tr2 = tr * tr;
GLfloat det = Det2x2( (GLfloat *) &vertices[0][0] );
GLfloat gap = sqrt( tr2 - (4.0f * det) );

printf("\n tr = %f , tr2 = %f, det= %f , gap = %f \n\n", tr, tr2, det, gap);
SetEigenValue(0, (tr + gap) / 2.0f);
SetEigenValue(1, (tr - gap) / 2.0f);

printf("\nEigenvalues of this 2x2 matrix are \n\n");
for( i = 0 ; i < 2 ; i++)
{
printf("\t %f \n", EigenValues[i]);
}

}


void SetEigenVector2( int idx, GLfloat x, GLfloat y)
{
EigenVectors[idx][0] = x;
EigenVectors[idx][1] = y;
}


void ComputeEigenVectors2()
{
int i;

SetEigenVector2(0, 3.0f, -1.0f);
SetEigenVector2(1, 1.0f, -2.0f);

printf("\nEigenvectors of this 2x2 matrix are \n\n");
for( i = 0 ; i < 2 ; i++)
{
printf("\t (%f) %f %f \n", EigenValues[i], EigenVectors[i][0], EigenVectors[i][1] );
}

}

void MakeArrays2()
{
ComputeVertices2();
ComputeEigenValues2();
ComputeEigenVectors2();
}

void DrawAxes2()
{
glBegin(GL_LINES);

glColor3f( 1.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 1.0f, 0.0f, 0.0f);

glColor3f(0.0f, 1.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 1.0f, 0.0f);

glEnd();
}

void DrawHeigenVectors2()
{
glBegin(GL_LINES);

glColor3f( 1.0f, 0.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3fv( &EigenVectors[0][0] );

glColor3f(0.0f, 1.0f, 0.0f);
glVertex3f( 0.0f, 0.0f, 0.0f);
glVertex3fv( &EigenVectors[1][0] );

glEnd();
}



void DrawVertices2()
{
int i;

glColor3f(1.0f, 1.0f, 1.0f);

glBegin(GL_LINES);

for( i = 0 ; i < 2 ; i++)
{
glVertex3f(0.0f, 0.0f, 0.0f);
glVertex3fv(vertices[i]);
}

glEnd();
}


void renderScene(void)
{

// Clear Color and Depth Buffers
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

// Reset transformations
glLoadIdentity();

// Set the camera
gluLookAt( 0.0f, 0.0f, 10.0f,
0.0f, 0.0f, 0.0f,
0.0f, 1.0f, 0.0f);

// Rotatge the scene
glScalef(0.7f, 0.7f, 0.7f);
glRotatef(angle, 1.0f, 1.0f, 1.0f);

// Set the line width to 2 for to have more visibles vectors
glLineWidth(2.0f);

// Draw X and Y 3D vectors
// DrawAxes2();

// Draw the matrix 3x3 matrix as 3x {x, y, z} vectors
DrawVertices2();

// Draw eigen vector of the matrix
DrawHeigenVectors2();

// update the animation for the next image
angle += angleInc;

// display the current image
glutSwapBuffers();
}


void changeSize(int w, int h)
{

// Prevent a divide by zero, when window is too short
// (you cant make a window of zero width).
if (h == 0)
h = 1;

float ratio = w * 1.0 / h;

// Use the Projection Matrix
glMatrixMode(GL_PROJECTION);

// Reset Matrix
glLoadIdentity();

// Set the viewport to be the entire window
glViewport(0, 0, w, h);

// Set the correct perspective.
gluPerspective(45.0f, ratio, 0.1f, 100.0f);

// Get Back to the Modelview
glMatrixMode(GL_MODELVIEW);
}

void keyboardFunc( unsigned char key, int x, int y )
{
switch ( key )
{
case 27: // Escape key

exit (0);
break;


case ' ' : // pause/play key

if( angleInc == 0.0f )
{
angleInc = 1.0f;
}
else
{
angleInc = 0.0f;
}
break;

}

glutPostRedisplay();
}

int main(int argc, char **argv)
{

// init GLUT and create window
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);
glutInitWindowPosition(100,100);
glutInitWindowSize(640,480);
glutCreateWindow("Lighthouse3D- GLUT Tutorial");

// register callbacks
glutDisplayFunc(renderScene);
glutReshapeFunc(changeSize);
glutKeyboardFunc(keyboardFunc);

MakeArrays2();

// here is the idle func registration
glutIdleFunc(renderScene);

// enter GLUT event processing cycle
glutMainLoop();

return 0;
}



It compute eigen-values using this formula and found goods eigen-values of 3 and -2 :)




void ComputeEigenValues2()
{
int i;

GLfloat tr = Trace2x2( (GLfloat *) &vertices[0][0] );
GLfloat tr2 = tr * tr;
GLfloat det = Det2x2( (GLfloat *) &vertices[0][0] );
GLfloat gap = sqrt( tr2 - (4.0f * det) );

printf("\n tr = %f , tr2 = %f, det= %f , gap = %f \n\n", tr, tr2, det, gap);
SetEigenValue(0, (tr + gap) / 2.0f);
SetEigenValue(1, (tr - gap) / 2.0f);

printf("\nEigenvalues of this 2x2 matrix are \n\n");
for( i = 0 ; i < 2 ; i++)
{
printf("\t %f \n", EigenValues[i]);
}
}



But I don't find the formula for to give eigen-vector at this page :(
So it does not really compute eigen-vector but only set them to value given at this page, so (1, -2) for the eigenvalue -2 and (3, -1) for the eigen-value 3




void ComputeEigenVectors2()
{
int i;

SetEigenVector2(0, 3.0f, -1.0f);
SetEigenVector2(1, 1.0f, -2.0f);

printf("\nEigenvectors of this 2x2 matrix are \n\n");
for( i = 0 ; i < 2 ; i++)
{
printf("\t (%f) %f %f \n", EigenValues[i], EigenVectors[i][0], EigenVectors[i][1] );
}
}



The output of the first code is this :




yannoo@Aerocool ~/Dev/Vpropre $ ./eigen2

The 2x2 matrix is

4.000000 3.000000
-2.000000 -3.000000

tr = 1.000000 , tr2 = 1.000000, det= -6.000000 , gap = 5.000000


Eigenvalues of this 2x2 matrix are

3.000000
-2.000000

Eigenvectors of this 2x2 matrix are

(3.000000) 3.000000 -1.000000
(-2.000000) 1.000000 -2.000000



What is the formula that I have to use for to compute eigen-vectors of the 2x2 matrix into the ComputeEigenVectors() func in a similar way of the computation of eigen-values into the ComputeEigenValues2() function ?

The 2x2 matrix example is from https://en.wikipedia.org/wiki/Eigenvalue_algorithm

GClements
11-08-2017, 08:12 PM
Having found the eigenvalues λ1 and λ2, the columns of A-λ1I are eigenvectors for λ2 and vice-versa (eigenvectors are only unique up to a scale factor). Some of those columns may be zero vectors (or very close to them), so you'd probably choose the column with the largest magnitude (as the columns will all be scaled multiples of each other, you only need to examine one element).

But it should be noted that finding eigenvalues and eigenvectors by solving the characteristic polynomial is impractical (and numerically unstable) for larger matrices. It's feasible for 3x3 matrices; it's theoretically possible for 4x4, but closed-form solutions for quartic polynomials are numerically unstable.

Most approaches use an iteration which converges either to an eigenvector or to a similar matrix (which will have the same eigenvalues as the original) which is triangular (the values along the diagonal of a triangular matrix are its eigenvalues). LAPACK uses the QR algorithm (https://en.wikipedia.org/wiki/QR_algorithm).

The Little Body
11-09-2017, 04:13 PM
The thing about what I think is something like to transform the original Laplacian matrix to a matrix where the diagonal are degrees values (or 1 / degree values) and where only a **directed** graph is represented at the top of this diagonal, cf **alls** values on the bottom of this diagonal are zeroes and where only somes values at the top of the diagonal are vertex to vertex indications (where -1 or -1 / degree on the original Laplacian matrix become complex or hyper-complex values into the transformed matrix)

In this case, the diagonal represent vertices degrees = eigen-values and matrix values after this degree/eigenvalue in the line "represent" (I know that is very more complex that this) the eigen-vector for the vertice concerned on this line , no ?
(I never studied eigen-values/vector before the end ot the last week, so I'm a very very ... very beginner in this domain :( )

But for to begin, can LAPACK to be used as a eigen-values/vectors resolver that can be used via an API inside a C/C++ OpenGL program ?
(cf. to be used instead the rigid formula that only handle 2x2 matrix inside ComputeEigenValues() and ComputeEigenVectors() calls)