Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 4 of 4

Thread: Laplacian, eigen-values and eigen-vectors

  1. #1
    Member Regular Contributor
    Join Date
    Jan 2011
    Location
    Paris, France
    Posts
    272

    Laplacian, eigen-values and eigen-vectors

    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

    Code :
    #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 ?
    Last edited by The Little Body; 11-07-2017 at 05:00 PM.
    @+
    Yannoo

  2. #2
    Member Regular Contributor
    Join Date
    Jan 2011
    Location
    Paris, France
    Posts
    272
    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


    Code :
     
    #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

    Code :
     
    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

    Code :
     
    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 :

    Code :
     
    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
    Last edited by The Little Body; 11-08-2017 at 05:02 PM.
    @+
    Yannoo

  3. #3
    Senior Member OpenGL Guru
    Join Date
    Jun 2013
    Posts
    2,467
    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.

  4. #4
    Member Regular Contributor
    Join Date
    Jan 2011
    Location
    Paris, France
    Posts
    272
    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)
    Last edited by The Little Body; 11-09-2017 at 04:45 PM.
    @+
    Yannoo

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •