I use a 4x4 affine transformation matrix to represent the location and orientation of objects in 3D space.

It's in my best interest to ensure that the x,y,z vectors (columns 1, 2 and 3) are orthogonal to eachother.

I'm wondering what is efficient way to go about ensuring this.

For example, lets say I have the matrix m set to a particular orientation. I want to now change its z vector to another arbitrary vector. But I want to ensure that it remains orthogonal.

Two methods I can think of would be:

1) Use cross products to redefine the other vectors in terms of the recently changed one:

y = z.cross(y).cross.z
x = z.cross(y);

2) Create the rotation matrix that would be needed to bring the z vector to its new orientation, multiply the entire matrix by it, thus rotating the other vectors as well.

The first method seems like it would be much more efficient, but it will always be redefining the unchanged vectors in terms of eachother. The second method would avoid that but is much less efficient.

Are there any other methods of dealing with this?

Why do you want to change one basis vector? If you rotate the object you have to change all of them, i.e., use an actual rotation matrix. If the other two vectors can be chosen arbitrarily, why do you store them anyway?

You basically just cross (product) two to create a third, then recross the third with the first (or second) one, and normalize them all.

If you start with only one vector you can cross it with an arbitrary up vector (0,1,0) to produce the third, then recross 1 and 3 to overwrite the up vector. Just make sure the original is not the same as the up vector.